Implementing and bounding a cascade heuristic for large-scale optimization
Guthrie, Katherine H.
Dell, Robert F.
Brown, Gerald G.
MetadataShow full item record
A cascade heuristic appeals when we are faced with a monolithic optimization model exhibiting more decision variables and/or constraints than can be accommodated by computers and/or 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 model's 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.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Carter, Jason W. (Monterey, California. Naval Postgraduate School, 1997-09);Heuristic methods of solving exploratory data analysis problems suffer from one major weakness - uncertainty regarding the optimality of the results. The developers of DaMI (Data Mining Initiative), a genetic algorithm ...
Lazzaro, Gary L. (Monterey, California: Naval Postgraduate School, 2016-06);The optimal defense and operation of networks against worst-case attack is an important problem for military analysts. We review development of existing solutions for the Defender-Attacker-Defender (DAD) tri-level optimization ...
Minimum-energy flight paths for UAVs using mesoscale wind forecasts and approximate dynamic programming Nachmani, Gil. (Monterey, California. Naval Postgraduate School, 2007-12);Fuel or battery consumption of unmanned aerial vehicles (UAVs) can be improved by utilizing or avoiding air currents. This thesis adopts a network modeling approach to formulate the problem of finding minimum energy ...