##
Re-optimization with the Primal-Dual Interior Point Method

###
J. Gondzio and A. Grothey

Re-optimization techniques for an interior point method applied to
solve a sequence of linear programming problems are discussed.
Conditions are given for problem perturbations that can be absorbed in
merely one Newton step. The analysis is performed for both short-step
and long-step feasible path-following method. A practical procedure is
then derived for an infeasible path-following method. It is applied in
the context of {\it crash} start for several large-scale structured
linear programs. Numerical results with OOPS, the new object-oriented
parallel solver demonstrate the efficiency of the approach. For large
structured linear programs crash start leads to about 40\% reduction
of the iterations number and translates into 25\% reduction of the
solution time. The crash procedure parallelizes well and speed-ups
between 3.1-3.8 on 4 processors are achieved.
Technical Report MS-01-004 Department of Mathematics and Statistics,
The University of Edinburgh, Scotland. July 27, 2001.

Contact: gondzio@maths.ed.ac.uk