关于图划分问题的改进的近似算法

本文考虑NP-难的极大图划分(MAX-GP)问题.我们给出应用半定规划(SDP) 松弛的一个一般方法,并且给出包括极大方向割,稠密子图,极大顶点覆盖,极大割,和极大反割在内的图划分问题的改进的近似比.     

无线网络中全调度问题的一种随机分布式算法

无线网络中的全调度,要确保网络中每个节点所可能的链路信息和广播信息都能无冲突地进行传输.通过简单的构造方法,证明了多项式时间内,能找到一个长度为$O(\bigtriangleup_{\rm out}^2\bigtriangleup_{\rm in})$的全调度;并且给出了全调度问题的一种随机分布式算法,证明了这种随机分布式算法,对任意的常数$h$,~$0     

软容量约束的动态设施选址问题的近似算法

考虑软容量约束的动态设施选址问题.假设设施的开放费用及连接费用都与时间有关,而且每一个设施均有容量约束.对此问题给出了第一个近似比为6的原始对偶(组合)算法.运行贪婪增加程序后,近似比进一步改进到3.7052.     

多层线性规划问题的整体优化算法

本文研究了求解多层线性规划问题的整体优化算法,利用流动等值面技术,证明了算法的有限终止性,并给出实际例子验证了算法的有效性.     

树网络上f模式最优广播问题的线性算法

网络G的一个结点v上的一次广播是指从它将一个消息传递给若干相邻结点.所谓f模式广播,是指结点v在一次广播中至多向f(v)个相邻结点传递信息(f为给定的整值函数).假定每一次广播的执行时间为一单位.网络G的广播过程是广播的时间安排,使所有结点均获得消息.最优广播问题是求总时间最少的广播过程.在G是树网络情形,文献中已给出时间界为O(n2)的算法.本文给出线性时间的简捷算法.     

线性规划流动等值面算法

对于线性规划问题,本文给出了基于流动等值面的等价模型,提出了一种不可行流动等值面算法．新算法保留了传统单纯形算法的优点并克服了它的不足。初步数值结果表明新算法比传统方法更为有效．     

APPROXIMATION ALGORITHM FOR MAX-BISECTION PROBLEM WITH THE POSITIVE SEMIDEFINITE RELAXATION

Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. In many interesting cases, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick. The main tool used to obtain this result is semidefinite programming.     

一种求解半定规划的邻近外梯度算法

本文提出了一种求解半定规划的邻近外梯度算法.通过转化半定规划的最优性条件为变分不等式,在变分不等式满足单调性和Lipschitz连续的前提下,构造包含原投影区域的半空间,产生邻近点序列来逼近变分不等式的解,简化了投影的求解过程.将该算法应用到教育测评问题中,数值实验结果表明,该方法是解大规模半定规划问题的一种可行方法.     

框式线性规划非精确不可行内点算法

本文为框式线性规划给出了一个非精确不可行内点算法．该算法使用的搜索方向仅需要达到一个相对的精度，这样的搜索方向可以通过Krylov子空间迭代法，比如CG或QMR得到，本文最后证明了算法的全局收敛性。     

Lagrangian Smoothing Heuristics for Max-Cut

This paper presents a smoothing heuristic for an NP-hard combinatorial problem. Starting with a convex Lagrangian relaxation, a pathfollowing method is applied to obtain good solutions while gradually transforming the relaxed problem into the original problem formulated with an exact penalty function. Starting points are drawn using different sampling techniques that use randomization and eigenvectors. The dual point that defines the convex relaxation is computed via eigenvalue optimization using subgradient techniques. The proposed method turns out to be competitive with the most recent ones. The idea presented here is generic and can be generalized to all box-constrained problems where convex Lagrangian relaxation can be applied. Furthermore, to the best of our knowledge, this is the first time that a Lagrangian heuristic is combined with pathfollowing techniques. The work was supported by the German Research Foundation (DFG) under grant No 421/2-1.     

线性规划的支撑方法（二）

线性规划的支撑方法（二）高学东，武森，李宗元（北京科技大学管理学院，北京１０００８３）６初始支撑可行解的构造６．１初始可行解的构造在研制或设计一种新产品的时候，初始设计往往可以用来帮助构造数学模型，相应的设计向量天虽不一定完全可行，但在某些方面有可能...     

求解随机凸规划概率约束问题的对偶算法

1引言随机规划中的概率约束问题在工程和管理中有广泛的应用.因为问题中包含非线性的概率约束,它们的求解非常困难.如果目标函数是线性的,问题的求解就比较容易.给出了一个求解随机线性规划概率约束问题的综述.原-对偶算法和切平面算法是比较有效的.在本文中,我们讨论随机凸规划概率约束问题:     

一种改进的进化规划算法及其收敛性

1　引　言进化算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法 ,主要包括遗传算法 ( genetic algorithms,GA)、进化规划 ( evolutionary programming,EP)和进化策略( evolution strategies,ES) [1 ] .遗传算法 ,进化策略和进化规划分别由 J.H.Holland,I.Rechenberg和 L.J.Fogel提出[2 ,3,4] .这些算法有许多相似性 ,且近年来都被应用于实值连续函数全局优化问题 ,并取得了较好的效果 .一些学者对进化算法的收敛性进行了分析[5,6,7,8] ,但总的说来 ,有关进化算法的理论研究成果目前还不是很多 ,尤其是进化规划和进化策略几…     

极小化总加权完工时间的Dial-a-Ride问题的在线随机算法

讨论一般度量空间上带单服务器的极小化总加权完工时间在线Dial-a-Ride问题.通过应用贪婪区间的技巧,提出了一个一般在线随机算法.根据这个算法,对于容量为1或者任意容量的一般度量空间上的在线Dial-a-Ride问题能得到一个竞争比为(2+√2)/ln(1+√2)的在线随机算法,这个算法不仅具有当前最好的竞争比,而且也改进了Krumke等人的结果.     

秩约束子集选择问题的分而治之解法

We consider the rank-constrained subset selection problem(RCSS):Given a matrix A and integer p≤rank(A),fing the largest submatrix A0 consisting of some colmns of A with rank(A0)=p.The RCSS problem is generally NP-hard.This paper focuses on a divide-and -conquer(DC)algorithm for solving the RCSS problem:Partition the matrix A into several small column blocks:A∏=[A1,…,Ak] with a certain column permutation ∏and decompose p to p1 p2 …pk such that solutions of the RCSS problems for smaller couples form a solution of the original RCSS problem.We show that the optimal solution of the RCSS problem can be found by DC algorithm for eachP≤rank (A),if and only if A is column-partitionable,i.e.,rank(A)=∑i=1^k rank(Ai),Based upon QR decomposition,a fast algorithm for determining the column partition is offered. Our divide-and-conquer algorithm is also quite efficient even A is approximately column-partitionable.     

DATA PREORDERING IN GENERALIZED PAV ALGORITHM FOR MONOTONIC REGRESSION

Monotonic regression （MR） is a least distance problem with monotonicity constraints induced by a partiaily ordered data set of observations. In our recent publication [In Ser. Nonconvex Optimization and Its Applications, Springer-Verlag, （2006） 83, pp. 25-33], the Pool-Adjazent-Violators algorithm （PAV） was generalized from completely to partially ordered data sets （posets）. The new algorithm, called CPAV, is characterized by the very low computational complexity, which is of second order in the number of observations. It treats the observations in a consecutive order, and it can follow any arbitrarily chosen topological order of the poset of observations. The CPAV algorithm produces a sufficiently accurate solution to the MR problem, but the accuracy depends on the chosen topological order. Here we prove that there exists a topological order for which the resulted CPAV solution is optimal. Furthermore, we present results of extensive numerical experiments, from which we draw conclusions about the most and the least preferable topological orders.     

A NEW TRUST-REGION ALGORITHM FOR FINITE MINIMAX PROBLEM

In this paper, a new trust region algorithm for minimax optimization problems is proposed, which solves only one quadratic subproblem based on a new approximation model at each iteration. The approach is different from the traditional algorithms that usually require to solve two quadratic subproblems. Moreover, to avoid Maratos effect, the nonmonotone strategy is employed. The analysis shows that, under standard conditions, the algorithm has global and superlinear convergence. Preliminary numerical experiments are conducted to show the efficiency of the new method.     

二供应商经济批量问题的多项式时间算法

为了从采购费用结构不同的供应商中找到最佳补货策略,考虑一个零售商从两个供应商补货的二供应商经济批量问题.零售商在两个供应商处的采购费用结构分别为复合安装费用和全单位数量折扣费用结构.通过对问题结构性质的分析论证,将问题的可行解转化为一个有向网络,降低问题求解的计算复杂性.综合动态规划和Dijkstra最短路算法证明了该问题是多项式时间可解的.     

Q2‖Cmax的对偶近似算法

本文讨论两台同类平行机排序问题,首先给出Ｍｕｌｔｉｆｉｔ算法在不同迭代初值下的紧界,然后利用一个新设计的对偶贪婪子过程构造出线性时间６／５－复合近似算法。     

反中心对称矩阵反问题解存在的条件

讨论了反中心对称矩阵反问题及其最佳逼近。研究了矩阵反问题有解的充分和必要条件,利用这类矩阵的结构和特征性质得到了矩阵反问题解的通式;证明了最佳逼近问题存在唯一解,并给出了求最佳逼近解的算法和数值算例。