J. Gondzio and A. Grothey
Abstract
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 crash start for several large-scale structured
linear programs. Numerical results with OOPS, a 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.
Key words: Re-optimization, Interior Point Methods, Crash Start.