ABSTRACT
Methods for representing the inverse of linear programming basis matrices are closely related to techniques for solving a system of sparse unsymmetric linear equations by direct methods. It is now well accepted that for these problems the static process of reordering the matrix in the lower block triangular (LBT) form constitutes the initial step. We introduce a combined static and dynamic factorisation of a basis matrix and derive its inverse which we call the partial elimination form of the inverse (PEFI). This factorisation takes advantage of the LBT structure and produces a sparser representation of the inverse than the elimination form of the inverse (EFI). In this we make use of the original columns (of the constraint matrix) which are in the basis. To represent the factored inverse it is, however, necessary to introduce special data structures which are used in the forward and the backward transformations (the two major algorithmic steps) of the simplex method. These two steps correspond to solving a system of equations defined by the basis matrix and solving a second system of equations defined by the transposed basis matrix. In this paper we compare the nonzero build up of PEFI with that of EFI and alternative methods for updating the basis inverse. The results of our experimental investigations are presented in this paper.
