Optimization Online


Maintaining a Basis Matrix in the Linear Programming Interior Point Method

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

Abstract: To precondition the normal equation system from the linear programming (LP) interior point method, basis preconditioners choose a basis matrix dependent on column scaling factors. Two criteria for choosing the basis matrix are compared which yield a maximum volume or maximum weight basis. Finding a maximum volume basis requires a combinatorial effort, but it gives a stronger bound on the condition number of the preconditioned normal matrix than the maximum weight basis. It is shown that neither of the two bases need to become an optimal LP basis as the interior point method approaches a solution. A crossover algorithm is presented to recover an optimal LP basis.

Keywords: Linear Programming, Basis Matrix, Interior Point Methods, Maximum Weight Basis, Maximum Volume Basis

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

Citation: Technical Report ERGO-17-009, University of Edinburgh, School of Mathematics

Download: [PDF]

Entry Submitted: 09/19/2017
Entry Accepted: 09/19/2017
Entry Last Modified: 09/19/2017

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