Reoptimization with the primal-dual interior point method

Research output: Contribution to journalArticlepeer-review

Abstract

Reoptimization techniques for an interior point method applied to solving 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 methods. 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 in the number of iterations and translates into a 25% reduction of the solution time. The crash procedure parallelizes well, and speed-ups between 3.1-3.8 on four processors are achieved.
Original languageEnglish
Pages (from-to)842-864
Number of pages23
JournalSiam journal on optimization
Volume13
Issue number3
DOIs
Publication statusPublished - 1 Jan 2003

Fingerprint

Dive into the research topics of 'Reoptimization with the primal-dual interior point method'. Together they form a unique fingerprint.

Cite this