##
A parallel implementation of an interior-point algorithm for multicommodity
network flows

###
Jordi Castro and Antonio Frangioni

A parallel implementation of the specialized interior-point algorithm
for multicommodity network flows introduced in \cite{Castro} is
presented. In this algorithm, the positive definite systems of each
iteration are solved through a scheme that combines direct
factorization and a preconditioned conjugate gradient (PCG) method.
Since the solution of at least $k$ independent linear systems is
required at each iteration of the PCG, $k$ being the number of
commodities, a coarse-grained parallellization of the algorithm
naturally arises, where these systems are solved on different
processors. Also, several other minor steps of the algorithm are
easily parallelized by commodity. An extensive set of computational
results on a shared memory machine is presented, using problems of up
to 2.5 million variables and 260,000 constraints. The results show
that the approach is especially competitive on large, difficult
multicommodity flow problems.
Report DR 2000-06,
Statistics and Operations Research Dept,
Universitat Politecnica de Catalunya,
Barcelona (Spain)

Contact: jcastro@eio.upc.es frangio@di.unipi.it