A Substitute Inverse for the Basis of a Staircase Structure Linear Program

The constraints of a staircase structure linear program are of the following form: A₁x₁ = d₁; B_t−1 + A_tx_t = d_t (t = 2, …, T). Letting m_i be the number of constraints m period i the substitute inverse consists of the inverse of T matrices which are m_i × m_i = 1, …, T, as opposed to the actual inverse which is m × m, m = ∑m_i. Updating the substitute inverse consists of updating some, but not necessarily all, of the T inverses. This may be done by appending one or more columns and pivoting on them or by adding a dyad matrix. Applications to the PILOT energy model will be discussed.