-

 

 

 




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: technical report ERGO-18-014, School of Mathematics, University of Edinburgh, Edinburgh EH9 3FD, Scotland, UK

Download: [PDF]

Entry Submitted: 09/20/2018
Entry Accepted: 09/20/2018
Entry Last Modified: 09/20/2018

Modify/Update this entry


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

 

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