##
A parallel interior-point algorithm for linear programming on
a shared memory machine

###
Erling D. Andersen and Knud D. Andersen

The XPRESS interior point optimizer is an ``industrial strength'' code
for solution of large-scale sparse linear programs. The purpose of the
present paper is to discuss how the XPRESS interior p oint optimizer
has been parallelized for a Silicon Graphics multi processor
computer. The major computational task, performed in each iteration of
the interior-point method implemented in the XPRESS interior point
optimizer is the solution of a symmetric and positive definite system
of linear equations. Therefore, parallelization of the Cholesky
decomposition and the triangular solve procedure are discussed in
detail. Finally, computational results are presented to demonstrate
the parallel efficiency of the optimizer. It should be emphasized that
the methods discussed can be applied to the solution of large-scale
sparse linear least squares problems.
CORE Discussion Paper 9808, CORE, Louvain-La-Neuve, Belgium, 1998.

Contact: eda@busieco.ou.dk