## 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 eort, 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.

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 eort, 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.

Original language | English |
---|---|

Number of pages | 11 |

Publication status | In preparation - Sep 2017 |