Reoptimization with the Primal-Dual Interior Point Method

Technical Report MS 01-004

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 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.

PDF MS01004.pdf.

Written: July 27, 2001, revised June 5, 2002 and July 31, 2002.
Published: SIAM Journal on Optimization 13(2003) 842-864.

Related Software:
OOPS Object-Oriented Parallel Solver.