#
Implementation of an Interior Point Method with Basis Preconditioning

###
Technical Report ERGO-18-014

**
L. Schork and
J. Gondzio
**

**
Abstract
**

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.

**
Key words:
**
Interior Point Methods, Linear Programming, Basis Preconditioning.

**
Text
**

PDF ERGO-18-014.pdf

**
History:
**

Written: September 20, 2018, revised February 2019.

*Mathematical Programming Computation*.

Published online: February 24, 2020.