A Cascade Approach for Staircase Linear Programs
Loading...
Authors
Baker, Steven F.
Rosenthal, Richard E.
Subjects
Advisors
Date of Issue
1998-07
Date
July 1998
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
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 model’s time periods, or other ordinally defined set. In turn, we bound the cascade’s deviation from the optimal
objective value by a Lagrangian cascade, which uses proximal cascade dual variables to penalize infeasibility. When tested on the
NPS/RAND Mobility Optimizer, a large temporal LF’ 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, 19971. We
also address methods to reduce the gap, including constraint extension of the Lagrulgian cascade, as well as a cut generation approach
similar to nested decomposition.
Type
Technical Report
Description
Series/Report No
Department
Operations Research
Organization
Identifiers
NPS Report Number
NPS-OR-98-004
Sponsors
Funder
Air Force Studies and Analyses Agency,
Washington, DC.
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.