Abstract
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).
Similar content being viewed by others
References
R.K. Ahuja, T.L. Magnanti and J.B. Orlin,Network Flows (Prentice-Hall, Englewood Cliffs, NJ, 1993).
E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, S. Ostrouchov and D. Sorensen,LAPACK Users’ Guide. (SIAM, Philadelphia, PA, 1992).
D.S. Atkinson and P.M. Vaidya, “A cutting plane algorithm that uses analytic centers,”Mathematical Programming 69 (1995) 1–43.
O. Bahn, J.-L. Goffin, J.-P. Vial and O. du Merle, “Experimental behaviour of an interior point cutting plane algorithm for convex programming: An application to geometric programming,”Discrete Applied Mathematics 49 (1994) 3–23.
O. Bahn, O. du Merle, J.-L. Goffin and J.-P. Vial, “A cutting plane method from analytic centers for stochastic programming,”Mathematical Programming 69 (1995) 45–73.
I.C. Choi and D. Goldfarb, “Exploiting special structure in a primal-dual path following algorithm,”Mathematical Programming 58 (1993) 33–52.
R.W. Cottle, “Manifestations of the Schur complement,”Linear Algebra and its Applications 8 (1974) 189–211.
G.B. Dantzig and P. Wolfe, “The decomposition algorithm for linear programming,”Econometrica 29 (4) (1961) 767–778.
G. de Ghellinck and J.-P. Vial, “A polynomial Newton method for linear programming,”Algorithmica 1 (1986) 425–453.
I.S. Duff, A.M. Erisman and J.K. Reid,Direct Methods for Sparse Matrices (Oxford University Press, New York, 1987).
J.M. Farvolden, W.B. Powell and I.J. Lustig, “A primal partitioning solution for the arc-chain formulation of a multicommodity network flow problem,”Operations Research 41 (1993) 669–603.
M. Fukushima, “On the dual approach to the traffic assignment problems,”Transportation Research B 18 (1984) 235–245.
E.M. Gafni and D.P. Bertsekas, “Two-metric projection methods for constrained optimization,”SIAM Journal on Control and Optimization 22 (6) (1984) 936–964.
P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, “Sparse matrix methods in optimization,”SIAM Journal on Scientific and Statistical Computing 5 (1984) 562–589.
J.-L. Goffin, A. Haurie and J.-P. Vial, “Decomposition and nondifferentiable optimization with the projective algorithm,”Management Science 38 (2) (1992) 284–302.
J.-L. Goffin, A. Haurie, J.-P. Vial and D.L. Zhu, “Using central prices in the decomposition of linear programs,”European Journal of Operational Research 64 (1993) 393–409.
J.-L. Goffin, Z. Luo, and Y. Ye, “On the complexity of a column generation algorithm for convex or quasiconvex feasibility problems,” in W.W. Hager, D.W. Hearn and P.M. Pardalos, eds.,Large Scale Optimization: State of the Art (Kluwer Academic Publishers, Dordrecht).
G.H. Golub and C. Van Loan.Matrix Computations, 2nd ed. (Johns Hopkins University Press, Baltimore, MD, 1989).
J. Gondzio and T. Terlaky, “A computational view of interior point methods for linear programming,” in J. Beasley, ed.,Advances in Linear and Integer Programming (Oxford University Press, Oxford) 1996, 103–144.
C.C. Gonzaga, “Path following methods for linear programming,”SIAM Review 34 (1992) 167–227.
D. Hearn and S. Lawphongpanich, “A dual ascent algorithm for traffic assignment problems,”Transportation Research B 24 (1990) 423–430.
D. Hearn, S. Lawphongpanich, and J. Ventura, “Restricted simplicial decomposition: Computation and extensions,”Mathematical Programming Study 31 (1987) 99–118.
A.L. Hipolito, “A weighted least squares approach to direction finding in mathematical programming,” Ph.D. Thesis, Dept. of Industrial Engineering, University of Florida, Gainesville, FL (1993).
K.L. Jones, I.J. Lustig, J.M. Farvolden and W.B. Powell, “Multicommodity network flows: The impact of formulation on decomposition,”Mathematical Programming 62 (1993) 95–117.
N. Karmarkar, “A new polynomial time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
J.E. Kelley, “The cutting plane method for solving convex programs,”Journal of the SIAM 8 (1960) 703–712.
K.C. Kiwiel,Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, Vol. 1133 (Springer, Berlin, 1985).
K.C. Kiwiel, “Proximity control in bundle methods for convex nondifferentiable optimization,”Mathematical Programming 46 (1990) 105–122.
L.S. Lasdon,Optimization Theory for Large Scale Systems (Macmillan, New York, 1970).
C. Lemaréchal, “Nondifferentiable optimization”, in G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd, eds.,Optimization, Handbooks in Operations Research and Management Science, Vol. 1, (North-Holland, Amsterdam, 1989) pp. 529–572.
C. Lemaréchal, A. Nemirovskii and Yu. Nesterov, “New variants of bundle methods,”Mathematical Programming 69 (1995) 177–204.
M. Minoux,Mathematical Programming: Theory and Algorithms (Wiley, New York, 1986).
J.E. Mitchell and M.J. Todd, “Solving combinatorial optimization problems using Karmarkar’s algorithm,”Mathematical Programming 56 (1992) 245–284.
Yu. Nesterov, “Cutting plane algorithms from analytic centers: Efficiency estimates.”Mathematical Programming. Series B 69 (1995) 149–176.
R. T. Rockafellar,Manotropic Flows and Network Optimizations (Wiley, New York, 1984).
H. Schramm and J. Zowe, “A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results.”SIAM Journal of Optimization 2 (1992) 1211–1252.
G. Sonnevend, “New algorithms in convex programming based on a notion of “centre” (for systems of analytic inequalities) and on rational extrapolation,” in: K.H. Hoffmann, J.B. Hiriat-Urruty, C. Lemarechal, and J. Zowe, eds.,Trends in Mathematical Optimization: Proceedings of the 4th French-German Conference on Optimization in Irsee, West-Germany, April 1986. Vol. 84 of International Series of Numerical Mathematics (Birkhäuser, Basel, 1988), pp. 311–327.
Y. Ye, “A potential reduction algorithm allowing column generation,”SIAM Journal on Optimization 2 (1992) 7–20.
Author information
Authors and Affiliations
Additional information
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.
Rights and permissions
About this article
Cite this article
Goffin, J.L., Gondzio, J., Sarkissian, R. et al. Solving nonlinear multicommodity flow problems by the analytic center cutting plane method. Mathematical Programming 76, 131–154 (1997). https://doi.org/10.1007/BF02614381
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02614381