A specialized interior point algorithm for multicommodity flows

Jordi Castro

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 to ensure 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.

Manuscript, July 1998
Statistics and Operations Research
Universitat Rovira i Virgili
43006 Tarragona (Spain)

Contact: jcastro@etse.urv.es