有使用限制的二台机器流水作业问题

本文研究了机器有使用限制的二台机器流水作业排序问题,目标为最小化最大完工时间,工件加工可以被机器的不可用时间段中断。我们讨论了两台机器上均有使用限制离线问题的可近似情形,并给出了性能比为3/2的近似算法。同时我们还考虑了在第二台机器上存在一个不可用时间段情况下的半在线问题,给出了一个竞争比为3/2的半在线算法。     

最大顶点覆盖问题的一种近似算法

给出了求解最大顶点覆盖问题的一种近似算法,讨论了它的性能保证,利用P ipage技术,为最大顶点覆盖问题设计出了0.75-近似算法.     

一类广义线性多乘积问题的完全多项式时间近似算法

本文针对一类广义线性多乘积问题提出一种求其全局最优解的完全多项式时间近似算法,并给出算法的理论分析和计算复杂性,数值结果表明本文算法有效可行.     

一类广义分式规划问题的ε-近似算法

本文针对一类广义分式规划问题提出一种求其全局最优解的ε-近似算法,并从理论上证明该算法的收敛性和计算复杂性,数值结果表明算法是有效可行的.     

优先序约束的排序问题：基于最大匹配的近似算法

本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题,目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时,两类问题在一般优先图上都是强NP-困难的,而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界,并基于许可工件之间的最大匹配设计近似算法,其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题,我们在理论上证明了算法的近似比为$2-\frac 2m$,其中$m$是机器数目。     

一类广义分式规划问题的ε-近似算法

 本文针对一类广义分式规划问题提出一种求其全局最优解的ε-近似算法,并从理论上证明该算法的收敛性和计算复杂性, 数值结果表明算法是有效可行的.     

优先序约束的排序问题：基于最大匹配的近似算法

本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题，目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时，两类问题在一般优先图上都是强NP-困难的，而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界，并基于许可工件之间的最大匹配设计近似算法，其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题，我们在理论上证明了算法的近似比为$2-\frac 2m$，其中$m$是机器数目。     

一类广义分式规划问题的完全多项式时间近似算法

本文对一类广义分式规划问题,提出一种求其全局最优解的完全多项式时间近似算法,给出该算法的理论分析和计算复杂性,通过数值算例验证该算法是有效可行的.     

排序问题的线性规划松弛方法

本文研究排序问题的线性规划松弛方法，对单台机器排序问题1｜prec｜∑wjCj介绍基于三个确定性线性规划松弛的2一近似算法，对平行机排序问题R｜rij｜（wjCj）介绍基于随机线性规划松弛的2-近似算法。这后一个算法对排序问题R｜（wjCj｜是3／2-近似算法．     

广义线性多乘积问题的完全多项式时间近似算法

本文针对广义线性多乘积极小化问题,通过一系列的线性规划问题的解提出一种求其全局最优解的完全多项式时间近似算法,并给出该算法的计算复杂性,且数值算例验证该算法是可行的.     

一个局部带优先权的最大多物资网络流问题

给出一个局部带优先权的最大多物资网络流问题(MMFP-LPRI),证明它的解存在,并给出其η-松弛解的定义.通过做辅助网络,并运用程丛电等根据Korte和Vygen于2000年在Young,Garg和K(o|¨)nemann等工作的基础上给出的求最大多种物资网络流问题的ε-近似解的多项式方案设计的一个算法作为子程序进行二分收索建立了一个求所给问题的η-松弛解的拟多项式算法.最后,进行算法分析,证明了所设计的算法的输出结果确实是MMFP-LPRT的一个η-松弛解.     

具有全局性公平满意度的最大多物资网络流问题

我们研究-个具有全局性公平满意度的最大多物资网络流问题(MMFP-GFMR).该项工作不仅丰富了最大多物资网络流问题的内容,而且可用于研究某些实际优化决策问题,例如运输过程中的一些资源分配问题.文中主要内容如下:(A)定义问题MMFP-GFMR并证明其解的存在性.(B)设计-个求解MMFP-GFMR的拟多项式逼近算法.(C)研究算法的复杂性与逼近程度.(D)最后通过模拟计算验证了我们的工作.     

An implementation of a parallel primal-dual interior point method for block-structured linear programs

An implementation of the primal-dual predictor-corrector interior point method is specialized to solve block-structured linear programs with side constraints. The block structure of the constraint matrix is exploited via parallel computation. The side constraints require the Cholesky factorization of a dense matrix, where a method that exploits parallelism for the dense Cholesky factorization is used. For testing, multicommodity flow problems were used. The resulting implementation is 65%–90% efficient, depending on the problem instance. For a problem with K commodities, an approximate speedup for the interior point method of 0.8K is realized.     

Local optimality conditions for multicommodity flow problems with separable piecewise convex costs

We consider here a multicommodity flow network optimization problem with non-convex but piecewise convex arc cost functions. We derive complete optimality conditions for local minima based on negative-cost cycles associated with each commodity. These conditions do not extend to the convex non-smooth case.     

A TRUST REGION ALGORITHM VIA BILEVEL LINEAR PROGRAMMING FOR SOLVING THE GENERAL MULTICOMMODITY MINIMAL COST FLOW PROBLEMS

This paper proposes a nonmonotonic backtracking trust region algorithm via bilevel linear programming for solving the general multicommodity minimal cost flow problems. Using the duality theory of the linear programming and convex theory, the generalized directional derivative of the general multicommodity minimal cost flow problems is derived. The global convergence and superlinear convergence rate of the proposed algorithm are established under some mild conditions.     

An Augmented Lagrangian Algorithm for Large Scale Multicommodity Routing

The linear multicommodity network flow (MCNF) problem has many applications in the areas of transportation and telecommunications. It has therefore received much attention, and many algorithms that exploit the problem structure have been suggested and implemented. The practical difficulty of solving MCNF models increases fast with respect to the problem size, and especially with respect to the number of commodities. Applications in telecommunications typically lead to instances with huge numbers of commodities, and tackling such instances computationally is challenging.In this paper, we describe and evaluate a fast and convergent lower-bounding procedure which is based on an augmented Lagrangian reformulation of MCNF, that is, a combined Lagrangian relaxation and penalty approach. The algorithm is specially designed for solving very large scale MCNF instances. Compared to a standard Lagrangian relaxation approach, it has more favorable convergence characteristics. To solve the nonlinear augmented Lagrangian subproblem, we apply a disaggregate simplicial decomposition scheme, which fully exploits the structure of the subproblem and has good reoptimization capabilities. Finally, the augmented Lagrangian algorithm can also be used to provide heuristic upper bounds.The efficiency of the augmented Lagrangian method is demonstrated through computational experiments on large scale instances. In particular, it provides near-optimal solutions to instances with over 3,600 nodes, 14,000 arcs and 80,000 commodities within reasonable computing time.     

Nonsmooth optimization methods for parallel decomposition of multicommodity flow problems

We develop an iterative algorithm based on right-hand side decomposition for the solution of multicommodity network flow problems. At each step of the proposed iterative procedure the coupling constraints are eliminated by subdividing the shared capacity resource among the different commodities and a master problem is constructed which attempts to improve sharing of the resources at each iteration.As the objective function of the master problem is nonsmooth, we apply to it a new optimization technique which does not require the exact solutions of the single commodity flow subproblems. This technique is based on the notion of - subgradients instead of subgradients and is suitable for parallel implementation. Extensions to the nonlinear, convex separable case are also discussed.The work of this author has been supported by the Air Force Office of Scientific Research Grant AFOSR-89-0410.     

广义多品种最小费用流问题的对偶理论

基于广义多品种最小费用流问题的性质，将问题转化成一对含有内、外层问题的双水平规划，内层规划实际是单品种费用流问题，而外层问题是分离的凸规划，使用相关的凸分析理论，导出了广义多品种最小费用流问题的对偶规划，对偶定理和Kuhn-Tucker条件。     

Capacity and flow assignment of data networks by generalized Benders decomposition

A mixed-integer non-linear model is proposed to optimize jointly the assignment of capacities and flows (the CFA problem) in a communication network. Discrete capacities are considered and the cost function combines the installation cost with a measure of the Quality of Service (QoS) of the resulting network for a given traffic. Generalized Benders decomposition induces convex subproblems which are multicommodity flow problems on different topologies with fixed capacities. These are solved by an efficient proximal decomposition method. Numerical tests on small to medium-size networks show the ability of the decomposition approach to obtain global optimal solutions of the CFA problem.     

Fast and simple approximation schemes for generalized flow

We present fast and simple fully polynomial-time approximation schemes (FPTAS) for generalized versions of maximum flow, multicommodity flow, minimum cost maximum flow, and minimum cost multicommodity flow. We extend and refine fractional packing frameworks introduced in FPTAS’s for traditional multicommodity flow and packing linear programs. Our FPTAS’s dominate the previous best known complexity bounds for all of these problems, some by more than a factor of n ², where n is the number of nodes. This is accomplished in part by introducing an efficient method of solving a sequence of generalized shortest path problems. Our generalized multicommodity FPTAS’s are now as fast as the best non-generalized ones. We believe our improvements make it practical to solve generalized multicommodity flow problems via combinatorial methods. Received: June 3, 1999 / Accepted: May 22, 2001?Published online September 17, 2001