Institution: Stanford University, Department of Computer Science

Title: Large-scale linear programming using the Cholesky factorization.

Author: Saunders, Michael A.

Date: January 1972

Abstract: A variation of the revised simplex method is proposed for solving the standard linear programming problem. The method is derived from an algorithm recently proposed by Gill and Murray, and is based upon the orthogonal factorization B = LQ or, equivalently, upon the Cholesky factorization ${BB}^T = {LL}^T$ where B is the usual square basis, L is lower triangular and Q is orthogonal. We wish to retain the favorable numerical properties of the orthogonal factorization, while extending the work of Gill and Murray to the case of linear programs which are both large and sparse. The principal property exploited is that the Cholesky factor L depends only on $underline{which}$ variables are in the basis, and not upon the $underline{order}$ in which they happen to enter. A preliminary ordering of the rows of the full data matrix therefore promises to ensure that L will remain sparse throughout the iterations of the simplex method. An initial (in-core) version of the algorithm has been implemented in Algol W on the IBM 360/91 and tested on several medium-scale problems from industry (up to 930 constraints). While performance has not been especially good on problems of high density, the method does appear to be efficient on problems which are very sparse, and on structured problems which have either generalized upper bounding, block-angular, or staircase form.

http://i.stanford.edu/pub/cstr/reports/cs/tr/72/252/CS-TR-72-252.pdf