Solving Large-Scale Linear Multicommodity Flow Problems with an Active Set Strategy and Proximal-ACCPM
Authors:
- 1 February 2006
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 54 (1) , 184-197
Abstract
In this paper, we propose to solve the linear multicommodity flow problem using a partial Lagrangian relaxation. The relaxation is restricted to the set of arcs that are likely to be saturated at the optimum. This set is itself approximated by an active set strategy. The partial Lagrangian dual is solved with Proximal-ACCPM, a variant of the analytic center cutting-plane method. The new approach makes it possible to solve huge problems when few arcs are saturated at the optimum, as appears to be the case in many practical problems.Keywords
This publication has 13 references indexed in Scilit:
- An Augmented Lagrangian Algorithm for Large Scale Multicommodity RoutingComputational Optimization and Applications, 2004
- Simplex and Interior Point Specialized Algorithms for Solving Nonoriented Multicommodity Flow ProblemsOperations Research, 2002
- A Decomposition-Based Pricing Procedure for Large-Scale Linear Programs: An Application to the Linear Multicommodity Flow ProblemManagement Science, 2000
- A Specialized Interior-Point Algorithm for Multicommodity Network FlowsSIAM Journal on Optimization, 2000
- A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min-Cost Flow ProblemsINFORMS Journal on Computing, 1999
- Solving nonlinear multicommodity flow problems by the analytic center cutting plane methodMathematical Programming, 1997
- A Primal Partitioning Solution for the Arc-Chain Formulation of a Multicommodity Network Flow ProblemOperations Research, 1993
- Decomposition and Nondifferentiable Optimization with the Projective AlgorithmManagement Science, 1992
- The Decomposition Algorithm for Linear ProgramsEconometrica, 1961
- A note on two problems in connexion with graphsNumerische Mathematik, 1959