A Substitute Inverse for the Basis of a Staircase Structure Linear Program.
Abstract
This report concerns a method for computing a substitute inverse for linear programs with a staircase structure. The constraints of a staircase structure linear program are of the following form: A(1)x(1)=d(1); B(t-1)x(t-1)+A(t)x(t) = d(t); (t = 2, ..., T). Letting m(i) be the number of constraints in period i, the substitute inverse consists of the inverse of T matrices which are m(i) x m(i), i = 1, ..., T as opposed to the actual inverse which is m x m, m = Sum over i m(i). Hence the substitute inverse would require significantly less storage than the actual inverse. Two methods are presented for updating the substitute inverse, both of which consist of updating some, but not necessarily all of the T smaller inverses. The first, a pivoting method, requires appending one or more columns to the smaller inverse and pivoting on the appended columns. The second requires adding one to T dyad matrices to the smaller inverses. Computational efficiency of both methods can be tested to a large degree using standard linear programming codes. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1976
- Accession Number
- ADA044904
Entities
People
- Richard D. Wollmer
Organizations
- Stanford University