A cascade approach for staircase linear programs with an application to Air Force mobility optimization
By: by Steven F. Baker
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1997
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 144
Subjects: LINEAR PROGRAMMING; OPTIMIZATION
Description: 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 approximation's      error. A feasible solution 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 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.
Notes: Dissertation supervisor, Richard E. Rosenthal.

Dissertation (Ph.D. in Operations Research) Naval Postgraduate School, June 1997.

Includes bibliographical references (p. 139-141)

Also available online.

System requirements: Adobe Acrobat reader.

dk/dk cc:9116 11/12/97.