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: [email protected]