A parallel primal-dual interior point method for multicommodity flow problems with quadratic costs

The authors present a parallel implementation of a primal-dual interior point method for multicommodity flow problems with separable quadratic costs. Exploiting the block structure of the problem, the system of linear equations to be solved at each iteration is decomposed into independent systems of linear equations associated with respective commodities and another system of linear equations corresponding to the coupling constraint. The authors solve them in parallel by applying the conjugate gradient (CG) method with an appropriate preconditioner, which significantly improves the speed of convergence of the CG method particularly when the generated feasible interior points approach the boundary of the non-negative orthant. Some devices are also introduced to reduce numerical errors caused by cancellation in executing the CG iterations. The authors implement the algorithm on the Connection Machine Model CM-5 under the control parallel programming environment. The computational results indicate that the proposed approach is very efficient for large-scale multicommodity flow problems. [In Japanese.]