×

A specialized interior-point algorithm for multicommodity network flows. (English) Zbl 0955.90087

Summary: 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.

MSC:

90C05 Linear programming
90C51 Interior-point methods
90C35 Programming involving graphs or networks
90C06 Large-scale problems in mathematical programming

Software:

IPM; PDNET; KORBX; PPRN
Full Text: DOI