A Cascade Approach for Staircase Linear Programs with an Application to Air Force Mobility Optimization.
NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Pagination or Media Count:
We develop a method to approximately solve a large staircase linear program that optimizes decisions over time. Also developed is a method to bound that approximations error. A feasible solution 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 penalizes infeasibility by incorporating dual information provided by the proximal cascade solution. When tested on a large temporal LP developed for US Air Force mobility planners, 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. We also address methods to reduce the gap, including constraint extension of the Lagrangian cascade, as well as exploitation of dual multipliers within the proximal cascade.
- Operations Research