A Specialized Interior-Point Algorithm for Multicommodity Network Flows
Author:
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 10 (3) , 852-877
Abstract
Despite the efficiency shown by interior-point methods in large-scale linear programming, they usually perform poorly when applied to multicommodity flow problems. The new specialized interior-point algorithm presented here overcomes this drawback. This specialization uses both a preconditioned conjugate gradient solver and a sparse Cholesky factorization to solve a linear system of equations at each iteration of the algorithm. The ad hoc preconditioner developed by exploiting the structure of the problem is instrumental in ensuring the efficiency of the method. An implementation of the algorithm is compared to state-of-the-art packages for multicommodity flows. The computational experiments were carried out using an extensive set of test problems, with sizes of up to 700,000 variables and 150,000 constraints. The results show the effectiveness of the algorithm.Keywords
This publication has 18 references indexed in Scilit:
- A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min-Cost Flow ProblemsINFORMS Journal on Computing, 1999
- An implementation of linear and nonlinear multicommodity network flowsEuropean Journal of Operational Research, 1996
- An exponential‐function reduction method for block‐angular convex programsNetworks, 1995
- A smooth penalty function algorithm for network-structured problemsEuropean Journal of Operational Research, 1995
- Solving a class of LP problems with a primal-dual logarithmic barrier methodEuropean Journal of Operational Research, 1995
- Block Sparse Cholesky Algorithms on Advanced Uniprocessor ComputersSIAM Journal on Scientific Computing, 1993
- An Implementation of the Dual Affine Scaling Algorithm for Minimum-Cost Flow on Bipartite Uncapacitated NetworksSIAM Journal on Optimization, 1993
- On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear ProgrammingSIAM Journal on Optimization, 1992
- An Interior Point Method for Block Angular OptimizationSIAM Journal on Optimization, 1991
- An implementation of Karmarkar's algorithm for linear programmingMathematical Programming, 1989