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

被引:78
作者
Goffin, JL [1 ]
Gondzio, J [1 ]
Sarkissian, R [1 ]
Vial, JP [1 ]
机构
[1] UNIV GENEVA, SECT MANAGEMENT STUDIES, HEC, LOGILAB, CH-1211 GENEVA 4, SWITZERLAND
基金
加拿大自然科学与工程研究理事会;
关键词
D O I
10.1007/BF02614381
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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).
引用
收藏
页码:131 / 154
页数:24
相关论文
共 38 条
[1]  
Ahuja RK., 1993, NETWORK FLOWS THEORY
[2]  
Anderson E., 1992, LAPACK User's Guide
[3]   A CUTTING PLANE ALGORITHM FOR CONVEX-PROGRAMMING THAT USES ANALYTIC CENTERS [J].
ATKINSON, DS ;
VAIDYA, PM .
MATHEMATICAL PROGRAMMING, 1995, 69 (01) :1-43
[4]   EXPERIMENTAL BEHAVIOR OF AN INTERIOR-POINT CUTTING PLANE ALGORITHM FOR CONVEX-PROGRAMMING - AN APPLICATION TO GEOMETRIC-PROGRAMMING [J].
BAHN, O ;
GOFFIN, JL ;
VIAL, JP ;
DUMERLE, O .
DISCRETE APPLIED MATHEMATICS, 1994, 49 (1-3) :3-23
[5]   A CUTTING PLANE METHOD FROM ANALYTIC CENTERS FOR STOCHASTIC-PROGRAMMING [J].
BAHN, O ;
DUMERLE, O ;
GOFFIN, JL ;
VIAL, JP .
MATHEMATICAL PROGRAMMING, 1995, 69 (01) :45-73
[6]   EXPLOITING SPECIAL STRUCTURE IN A PRIMAL DUAL PATH-FOLLOWING ALGORITHM [J].
CHOI, IC ;
GOLDFARB, D .
MATHEMATICAL PROGRAMMING, 1993, 58 (01) :33-52
[7]  
Cottle R. W., 1974, LINEAR ALGEBRA APPL, V8, P189
[8]   THE DECOMPOSITION ALGORITHM FOR LINEAR-PROGRAMS [J].
DANTZIG, GB ;
WOLFE, P .
ECONOMETRICA, 1961, 29 (04) :767-778
[9]   A Polynomial Newton Method for Linear Programming [J].
de Ghellinck, Guy ;
Vial, Jean-Philippe .
ALGORITHMICA, 1986, 1 (1-4) :425-453
[10]  
DUFF IS, 1987, DIRECT METHODS SPARS