On Exploiting Original Problem Data in the Inverse Representation of Linear Programming Bases

A method for handling the inverse of linear programming bases is presented. The method extensively exploits the fact that the original problem data (i.e., the constraint matrix) must be stored anyway. It then builds the basis inverse representation of two matrices: an easily invertible submatrix of the constraint matrix (fundamental basis) and a Schur complement containing information on the difference between the fundamental and the current bases. Since the fundamental basis does not have to be stored, the memory space required by the method is limited to that for a small, dense Schur complement. Computational comparisons are made with advanced implementations of LU factorizations with Bartels-Golub updating. Tests performed on real-life linear programs from the Netlib collection indicate that the method may be used for solving large problems.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.