Implementation of an Interior Point Method with Basis Preconditioning

Lukas Schork, Jacek Gondzio

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

The implementation of a linear programming interior point solver is described that is based on iterative linear algebra. The linear systems are preconditioned by a basis matrix, which is updated from one interior point iteration to the next to bound the entries in a certain tableau matrix. The update scheme is based on simplex-type pivot operations and is implemented using linear algebra techniques from the revised simplex method. An initial basis is constructed by a crash procedure after a few interior point iterations. The basis at the end of the interior point solve provides the starting basis for a crossover method which recovers a basic solution to the linear program. Results of a computational study on a diverse set of medium to large-scale problems are discussed.
Original languageEnglish
Pages (from-to)603–635
Number of pages24
JournalMathematical Programming Computation
Early online date24 Feb 2020
Publication statusPublished - 31 Dec 2020


Dive into the research topics of 'Implementation of an Interior Point Method with Basis Preconditioning'. Together they form a unique fingerprint.

Cite this