A Branch-and-Bound Algorithm for Concave Network Flow Problems

In this paper a Branch-and-Bound (BB) algorithm is developed to obtain an optimal solution to the single source uncapacitated minimum cost Network Flow Problem (NFP) with general concave costs. Concave NFPs are NP-Hard, even for the simplest version therefore, there is a scarcity of exact methods to address them in their full generality. The BB algorithm presented here can be used to solve optimally single source uncapacitated minimum cost NFPs with any kind of concave arc costs. The bounding is based on the computation of lower bounds derived from state space relaxations of a dynamic programming formulation. The relaxations, which are the subject of the paper (Fontes et al., 2005b) and also briefly discussed here, involve the use of non-injective mapping functions, which guarantee a reduction on the cardinality of the state space. Branching is performed by either fixing an arc as part of the final solution or by removing it from the final solution. Computational results are reported and compared to available alternative methods for addressing the same type of problems. It could be concluded that our BB algorithm has better performance and the results have also shown evidence that it has a sub-exponential time growth.     

Lower Bounds for Covering Problems

In this paper we present an (nlogn) lower bound proof for several covering problems including the optimal line bipartition problem, min-max covering by two axis parallel rectangles, discrete and continuous two-center problems, two-line center problem, etc. Our proofs are based on using the rotational reduce technique and well-known lower bound for the maximal gap problem.     

The Minimum Concave Cost Network Flow Problem with fixed numbers of sources and nonlinear arc costs

We prove that the Minimum Concave Cost Network Flow Problem with fixed numbers of sources and nonlinear arc costs can be solved by an algorithm requiring a number of elementary operations and a number of evaluations of the nonlinear cost functions which are both bounded by polynomials inr, n, m, wherer is the number of nodes,n is the number of arcs andm the number of sinks in the network.On leave from Institute of Mathematics, P.O. Box 631, Bo Ho, Hanoi, Vietnam.     

On the Applicability of Lower Bounds for Solving Rectilinear Quadratic Assignment Problems in Parallel

The quadratic assignment problem (QAP) belongs to the hard core of NP-hard optimization problems. After almost forty years of research only relatively small instances can be solved to optimality. The reason is that the quality of the lower bounds available for exact methods is not sufficient. Recently, lower bounds based on decomposition were proposed for the so called rectilinear QAP that proved to be the strongest for a large class of problem instances. We investigate the strength of these bounds when applied not only at the root node of a search tree but as the bound function used in a Branch-and-Bound code solving large scale QAPs.     

几何凸（凹）函数积分的上（下）界比较及其一般结果

运用齐次函数的分析性质,在基本不等式中插入了一个齐次加权＂平均＂,推广加细了基本不等式.作为特例,得到了加权的对数,指数平均不等式,从而部分解决了文[1]提出的问题.     

Constraint Generation for Network Reliability Problems

This paper presents a constraint generation approach to the network reliability problem of adding spare capacity at minimum cost that allows the traffic on a failed link to be rerouted to its destination. Any number of non-simultaneous link failures can be part of the requirements on the spare capacity. The key result is a necessary and sufficient condition for a multicommodity flow to exist, which is derived in the appendix. Computational results on large numbers of random networks are presented.     

可靠性网络中费用最小化问题的一种新的分枝定界算法

本文对可靠性网络中串-并系统的费用最小化问题提出一种新的分枝定界算法.我们根据这类网络的特殊结构和性质,建立了新的最优性必要条件,在分枝搜索过程中增加新的剪枝准则,从而加速了算法的收敛速度.有效的数值试验表明,该算法可求解大规模可靠性网络的费用最小化问题.     

Linear Approximations in a Dynamic Programming Approach for the Uncapacitated Single-Source Minimum Concave Cost Network Flow Problem in Acyclic Networks

We consider minimum concave cost flow problems in acyclic, uncapacitated networks with a single source. For these problems a dynamic programming scheme is developed. It is shown that the concave cost functions on the arcs can be approximated by linear functions. Thus the considered problem can be solved by a series of linear programs. This approximation method, whose convergence is shown, works particularly well, if the nodes of the network have small degrees. Computational results on several classes of networks are reported.     

运输网络中求最小费用最大流的一个算法

给出一个求动输网络中的最小费用最大流的数值算法,证明了算法的理论依据,并举例说明算法的应用。     

Global State Space Approach for the Efficient Numerical Solution of State-Constrained Trajectory Optimization Problems

A new approach based on a global state space form is introduced for solving trajectory optimization problems with state inequality constraints via indirect methods. The use of minimal coordinates on a boundary arc of the state constraint eliminates severe problems, which occur for standard methods and are due to the appearance of differential-algebraic boundary-value problems. Together with a hybrid approach and a careful treatment of some interior-point conditions, we obtain an efficient and reliable solution method.     

Implementation and Test of Auction Methods for Solving Generalized Network Flow Problems with Separable Convex Cost

We describe the implementation and testing of two methods, based on the auction approach, for solving the problem of minimizing a separable convex cost subject to generalized network flow conservation constraints. The first method is the -relaxation method of Ref. 1; the second is an extension of the auction sequential/shortest path algorithm for ordinary network flow to generalized network flow. We report test results on a large set of randomly generated problems with varying topology, arc gains, and cost function. Comparison with the commercial code CPLEX on linear/quadratic cost problems and with the public-domain code PPRN on nonlinear cost ordinary network problems are also made. The test results show that the auction sequential/shortest path algorithm is generally fastest for solving quadratic cost problems and mixed linear/nonlinear cost problems with arc gain range near 1. The -relaxation method is generally fastest for solving nonlinear cost ordinary network problems and mixed linear/nonlinear cost problems with arc gain range away from 1. CPLEX is generally fastest for solving linear cost and mixed linear/quadratic cost problems with arc gain range near 1.