Optimization Online


Implementation of an Interior Point Method with Basis Preconditioning

L. Schork (L.Schork***at***ed.ac.uk)
J. Gondzio (J.Gondzio***at***ed.ac.uk)

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.

Keywords: Linear Programming, Interior Point Methods, Basis Preconditioning, Crossover

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Math. Prog. Comp. (2020). https://doi.org/10.1007/s12532-020-00181-8


Entry Submitted: 09/20/2018
Entry Accepted: 09/20/2018
Entry Last Modified: 03/08/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society