L. Schork and J. Gondzio
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.
Key words: Linear Programming, Basis Matrix, Interior Point Methods, Maximum Weight Basis, Maximum Volume Basis.