Construction of LU Factors of the Basis to Reduce Build-Up during Simplex Iterations

Abstract

Algorithms for the inversion of a sparse square matrix have generally been designed with the aim of minimizing the number of calculations required to factorize the matrix and to solve for one or more right-hand sides. This usually involves attempting to minimize the number of non-zeros in the factors of the inverse. An inversion routine for use in the product-form simplex method must satisfy a rather different requirement. The inverse is updated during iterations to reflect changes in the basis, and additional non-zeros created by updating become significant. We consider the use of various forms of the Hellerman-Rarick P4 inversion algorithm in conjunction with the Forrest-Tomlin update of the factors, and suggest a heuristic for selection between these forms during the inversion process.

Keywords:

• Linear Programming
• Inversion
• Sparse Matrices