Accession Number : ADA324288

Title :   A Cascade Approach for Staircase Linear Programs with an Application to Air Force Mobility Optimization.

Descriptive Note : Doctoral thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s) : Baker, Steven F.

PDF Url : ADA324288

Report Date : JUN 1997

Pagination or Media Count : 167

Abstract : 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.

Descriptors :   *OPTIMIZATION, *LINEAR PROGRAMMING, MATHEMATICAL MODELS, ALGORITHMS, TIME DEPENDENCE, THESES, APPROXIMATION(MATHEMATICS), MILITARY APPLICATIONS, HEURISTIC METHODS, SYSTEMS ANALYSIS, AIR FORCE OPERATIONS, AIRMOBILE OPERATIONS, LAGRANGIAN FUNCTIONS.

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE