A Cascade Approach for Staircase Linear Programs

We develop a method to approximately solve a large staircase linear program that optimizes decisions over multiple time periods. A bound on the approximation error is also developed. The approximation is derived by a proximal cascade, which sequentially considers overlapping subsets of the models time periods, or other ordinally defined set. In turn, we bound the cascades deviation from the optimal objective value by a Lagrangian cascade, which uses proximal cascade dual variables to penalize in feasibility. When tested on the NPSRAND Mobility Optimizer, a large temporal LP developed for the US Air Force, we often observe gaps between the approximation and bound of less than 10 percent, and save as much as 80 percent of the time required to solve the original problem Baker, 1997. We also address methods to reduce the gap, including constraint extension of the Lagrangian cascade, as well as a cut generation approach similar to nested decomposition.