Accession Number:



Implementing and Bounding a Cascade Heuristic for Large-Scale Optimization

Personal Author(s):

Corporate Author:

Naval Postgraduate School Monterey United States

Report Date:



A cascade heuristic appeals when we are faced with a monolithic optimization model exhibiting more decision variables andor constraints than can be accommodated by computers andor optimization software available. This thesis studies the implementation and bounding of a cascade heuristic by using the integer linear program implementations of two applications, a production model PM and the USMC Hornet Assignment Sundown Model HASMa. While the solutions for PM are within 5 of the optimal solution for a wide variety of cascade heuristic implementations, the solutions for HASMa deviate, in some cases, by over 99 of the optimal solution. To provide a metric for the quality of a cascade heuristic solution, we produce a lower bound for the optimal objective function value by aggregating segments of each models periods. For PM, the aggregated models produce lower bounds all within 2 of the optimal objective function value. For HASMa, the lower bounds can be up to 50 from the optimal objective function value but are within 10 of optimal when the aggregation includes just one-third of the periods. In both cases, finding a lower bound for the optimal objective function value provides significant insight to the quality of the cascade heuristic solution.

Descriptive Note:

Technical Report



Subject Categories:

Communities Of Interest:

Distribution Statement:

Approved For Public Release;

File Size: