Optimal Two-commodity Flows with Non-linear Cost Functions

We consider networks in which two different commodities have to be transported across undirected arcs, subject to a shared capacity on the arcs. For each arc and commodity there is an associated non-linear cost that depends on the amount of the commodity transported across the arc. The aim is to minimize the sum of the costs over all arcs and commodities. Efficient algorithms for solving this problem for two types of objective functions will be presented: in the first the cost depends on the absolute value of the flow and in the second the cost is a quadratic function of the flow. Previous work on multi-commodity flow has concentrated on linear cost problems or tackled non-linear cost problems with Lagrangian relaxation methods and other more general techniques. The algorithms in this paper, on the other hand, provide a very efficient way of dealing with two types of non-linear two-commodity optimal flow problems.     

An Algorithm for Non-Linear Network Programming: Implementation,Results and Comparisons

This paper evaluates an algorithm for solving network flow optimization problems with quadratic cost functions. Strategies for fast implementation are discussed and the results of extensive numerical tests are given. The performance of the algorithm measured by CPU time is compared with that of the convex simplex method specialized for quadratic network programming. Performance of the two methods is analysed with respect to network size and density, and other parameters of interest. The algorithm is shown to perform significantly better on the majority of problems. We also show how the algorithm may be used to solve non-linear convex network optimization problems by the use of sequential quadratic programming.     

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.     

Optimal expansion of capacitated transshipment networks

In this paper, we address the problem of allocating a given budget to increase the capacities of arcs in a transshipment network to minimize the cost of flow in the network. The capacity expansion costs of arcs are assumed to be piecewise linear convex functions. We use properties of the optimum solution to convert this problem into a parametric network flow problem. The concept of optimum basis structure is used which allows us to consider piecewise linear convex functions without introducing additional arcs. The resulting algorithm yields an optimum solution of the capacity expansion problem for all budget levels less than or equal to the given budget. For integer data, the algorithm performs almost all computations in integers. Detailed computational results are also presented.     

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.     

Maximization of the Ratio of Two Convex Quadratic Functions over a Polytope

In this paper, we will develop an algorithm for solving a quadratic fractional programming problem which was recently introduced by Lo and MacKinlay to construct a maximal predictability portfolio, a new approach in portfolio analysis. The objective function of this problem is defined by the ratio of two convex quadratic functions, which is a typical global optimization problem with multiple local optima. We will show that a well-designed branch-and-bound algorithm using (i) Dinkelbach's parametric strategy, (ii) linear overestimating function and (iii) -subdivision strategy can solve problems of practical size in an efficient way. This algorithm is particularly efficient for Lo-MacKinlay's problem where the associated nonconvex quadratic programming problem has low rank nonconcave property.     

Network simplex algorithm for the general equal flow problem

In this paper the general equal flow problem is considered. This is a minimum cost network flow problem with additional side constraints requiring the flow of arcs in some given sets of arcs to take on the same value. This model can be applied to approach water resource system management problems or multiperiod logistic problems in general involving policy restrictions which require some arcs to carry the same amount of flow through the given study period. Although the bases of the general equal flow problem are no longer spanning trees, it is possible to recognize a similar structure that allows us to take advantage of the practical computational capabilities of network models. After characterizing the bases of the problem as good (r+1)-forests, a simplex primal algorithm is developed that exploits the network structure of the problem and requires only slight modifications of the well-known network simplex algorithm.     

Solving nonlinear multicommodity flow problems by the analytic center cutting plane method

The paper deals with nonlinear multicommodity flow problems with convex costs. A decomposition method is proposed to solve them. The approach applies a potential reduction algorithm to solve the master problem approximately and a column generation technique to define a sequence of primal linear programming problems. Each subproblem consists of finding a minimum cost flow between an origin and a destination node in an uncapacited network. It is thus formulated as a shortest path problem and solved with Dijkstra’s d-heap algorithm. An implementation is described that takes full advantage of the supersparsity of the network in the linear algebra operations. Computational results show the efficiency of this approach on well-known nondifferentiable problems and also large scale randomly generated problems (up to 1000 arcs and 5000 commodities). This research has been supported by the Fonds National de la Recherche Scientifique Suisse, grant #12-34002.92, NSERC-Canada and FCAR-Quebec. This research was supported by an Obermann fellowship at the Center for Advanced Studies at the University of Iowa.     

A parametric algorithm for convex cost network flow and related problems

The convex cost network flow problem is to determine the minimum cost flow in a network when cost of flow over each arc is given by a piecewise linear convex function. In this paper, we develop a parametric algorithm for the convex cost network flow problem. We define the concept of optimum basis structure for the convex cost network flow problem. The optimum basis structure is then used to parametrize v, the flow to be transsshipped from source to sink. The resulting algorithm successively augments the flow on the shortest paths from source to sink which are implicitly enumerated by the algorithm. The algorithm is shown to be polynomially bounded. Computational results are presented to demonstrate the efficiency of the algorithm in solving large size problems. We also show how this algorithm can be used to (i) obtain the project cost curve of a CPM network with convex time-cost tradeoff functions; (ii) determine maximum flow in a network with concave gain functions; (iii) determine optimum capacity expansion of a network having convex arc capacity expansion costs.     

线性等式约束多目标规划的一个降维算法

本文提出具有线性等式约束多目标规划问题的一个降维算法．当目标函数全是二次或线性但至少有一个二次型时，用线性加权法转化原问题为单目标二次规划，再用降维方法转化为求解一个线性方程组．若目标函数非上述情形，首先用线性加权法将原问题转化为具有线性等式约束的非线性规划，然后，对这一非线性规划的目标函数二次逼近，构成线性等式约束二次规划序列，用降维法求解，直到满足精度要求为止．     

Maximum flow in a network with fuzzy arc capacities

Our main concern is the maximum flow in a network in which an excess over the beforehand fixed quota of arc capacity is admissible. The problem is represented as a partially fuzzy linear programming task. A theorem equivalent to the Ford and Fulkerson one concerning the classic task of maximum flow is proved in the paper. An algorithm for searching maximum flow assuming integer values of flows on network arcs is presented.     

A polynomial algorithm for minimum quadratic cost flow problems

Network flow problems with quadratic separable costs appear in a number of important applications such as; approximating input-output matrices in economy; projecting and forecasting traffic matrices in telecommunication networks; solving nondifferentiable cost flow problems by subgradient algorithms. It is shown that the scaling technique introduced by Edmonds and Karp (1972) in the case of linear cost flows for deriving a polynomial complexity bound for the out-of-kilter method, may be extended to quadratic cost flows and leads to a polynomial algorithm for this class of problems. The method may be applied to the solution of singly constrained quadratic programs and thus provides an alternative approach to the polynomial algorithm suggested by Helgason, Kennington and Lall (1980).     

A conic quadratic formulation for a class of convex congestion functions in network flow problems

In this paper we consider a multicommodity network flow problem with flow routing and discrete capacity expansion decisions. The problem involves trading off congestion and capacity assignment (or expansion) costs. In particular, we consider congestion costs involving convex, increasing power functions of flows on the arcs. We first observe that under certain conditions the congestion cost can be formulated as a convex function of the capacity level and the flow. Then, we show that the problem can be efficiently formulated by using conic quadratic inequalities. As most of the research on this problem is devoted to heuristic approaches, this study differs in showing that the problem can be solved to optimum by branch-and-bound solvers implementing the second-order cone programming (SOCP) algorithms. Computational experiments on the test problems from the literature show that the continuous relaxation of the formulation gives a tight lower bound and leads to optimal or near optimal integer solutions within reasonable CPU times.     

A Primal-Dual Algorithm for Monotropic Programming and its Application to Network Optimization

This paper presents a new primal-dual algorithm for solving a class of monotropic programming problems. This class involves many problems arising in a number of important applications in telecommunications networks, transportation and water distribution. The proposed algorithm is inspired by Kallio and Ruszczyski approach for linear programming [M. Kallio and A. Ruszczyski, WP-94-15, IIASA, 1994]. The problem is replaced by a game using two different augmented Lagrangian functions defined for the primal and the dual problems. It is then possible to develop a block-wise Gauss-Seidel method to reach an equilibrium of the game with alternating steps made in each component of the primal and dual variables. Finally, we show how this algorithm may be applied to some important problems in Network Optimization such as the minimum quadratic cost single flow problems and convex multicommodity flow problems.     

A derivative algorithm for inexact quadratic program – application to environmental decision-making under uncertainty

Inexact quadratic programming (IQP) is an extension of conventional quadratic programming for handling both nonlinearities in cost objectives and uncertainties with modeling parameters. It has been a useful tool for environmental systems analysis. However, inefficiency in its solution method has existed, leading to difficulties in its practical application. In this study, a derivative algorithm (DAM) is proposed for solving the IQP. It improves upon the existing method through provision of a quantitative expression for uncertain relationships between the quadratic objective function and the decision variables. The DAM requires much lower computational efforts than the existing algorithm, which is especially meaningful for the IQP's application to large-scale problems. The developed DAM is applied to a hypothetical problem of municipal solid waste management and planning. Detailed solution steps are provided to clearly demonstrate the method's advantages.     

Parametric simplex algorithms for solving a special class of nonconvex minimization problems

It is shown that parametric linear programming algorithms work efficiently for a class of nonconvex quadratic programming problems called generalized linear multiplicative programming problems, whose objective function is the sum of a linear function and a product of two linear functions. Also, it is shown that the global minimum of the sum of the two linear fractional functions over a polytope can be obtained by a similar algorithm. Our numerical experiments reveal that these problems can be solved in much the same computational time as that of solving associated linear programs. Furthermore, we will show that the same approach can be extended to a more general class of nonconvex quadratic programming problems.     

基于增广Lagrange函数的RQP方法

Recursive quadratic programming is a family of techniques developd by Bartholomew-Biggs and other authors for solving nonlinear programming problems.This paperdescribes a new method for constrained optimization which obtains its search di-rections from a quadratic programming subproblem based on the well-known aug-mented Lagrangian function.It avoids the penalty parameter to tend to infinity.We employ the Fletcher‘s exact penalty function as a merit function and the use of an approximate directional derivative of the function that avoids the need toevaluate the second order derivatives of the problem functions.We prove that thealgorithm possesses global and superlinear convergence properties.At the sametime, numerical results are reported.     

Relaxation techniques for strictly convex network problems

Gauss—Seidel type relaxation techniques are applied in the context of strictly convex pure networks with separable cost functions. The algorithm is an extension of the Bertsekas—Tseng approach for solving the linear network problem and its dual as a pair of monotropic programming problems. The method is extended to cover the class of generalized network problems. Alternative internal tactics for the dual problem are examined. Computational experiments — aimed at the improved efficiency of the algorithm — are presented.This research was supported in part by National Science Foundation Grant No. DCR-8401098-A01.     

A smoothing Newton algorithm based on a one-parametric class of smoothing functions for linear programming over symmetric cones

In this paper, we introduce a one-parametric class of smoothing functions which contains the Fischer–Burmeister smoothing function and the CHKS smoothing function as special cases. Based on this class of smoothing functions, a smoothing Newton algorithm is extended to solve linear programming over symmetric cones. The global and local quadratic convergence results of the algorithm are established under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool in our analysis.     

求解摩擦接触问题的一个非内点光滑化算法

给出了一个求解三维弹性有摩擦接触问题的新算法,即基于NCP函数的非内点光滑化算法．首先通过参变量变分原理和参数二次规划法,将三维弹性有摩擦接触问题的分析归结为线性互补问题的求解;然后利用NCP函数,将互补问题的求解转换为非光滑方程组的求解;再用凝聚函数对其进行光滑化,最后用NEWTON法解所得到的光滑非线性方程组．方法具有易于理解及实现方便等特点．通过线性互补问题的数值算例及接触问题实例证实了该算法的可靠性与有效性．