Implementing and bounding a cascade heuristic for large-scale optimization
Author
Guthrie, Katherine H.
Date
2017-06Advisor
Dell, Robert F.
Second Reader
Brown, Gerald G.
Metadata
Show full item recordAbstract
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.
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.Related items
Showing items related by title, author, creator and subject.
-
Testing effectiveness of genetic algorithms for exploratory data analysis
Carter, Jason W. (Monterey, California. Naval Postgraduate School, 1997-03);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 ... -
Tri-level optimization algorithms for solving defender-attacker- defender network models
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 ... -
A sliding time window heuristic for open pit mine block sequencing
Cullenbine, Christopher; Wood, R. Kevin; Newman, Alexandra (2012);The open pit mine block sequencing problem (OPBS) seeks a discrete-time production schedule that maximizes the net present value of the orebody extracted from an open pit mine. This integer program (IP) discretizes the ...