The simplex method of linear programming using LU decomposition

TLDR

Standard computer implementations of Dantzig's simplex method for linear programming are based upon forming the inverse of the basic matrix and updating the inverse after every step of the method. The paper proposes an implementation of the simplex method using LU decomposition of the basic matrix. The method uses LU decomposition with row interchanges to compute the basic matrix, avoiding explicit inversion. The LU‑based implementation is slower than conventional inverse‑based versions but exhibits superior round‑off error behavior, and is published as CACM Algorithm 350.

Abstract

Standard computer implementations of Dantzig's simplex method for linear programming are based upon forming the inverse of the basic matrix and updating the inverse after every step of the method. These implementations have bad round-off error properties. This paper gives the theoretical background for an implementation which is based upon the LU decomposition, computed with row interchanges, of the basic matrix. The implementation is slow, but has good round-off error behavior. The implementation appears as CACM Algorithm 350.