Publication:
Implementing and bounding a cascade heuristic for large-scale optimization

Loading...
Thumbnail Image
Authors
Guthrie, Katherine H.
Subjects
cascade heuristic
cascade optimization
F/A-18
production model
bounding objective function values
Advisors
Dell, Robert F.
Date of Issue
2017-06
Date
Jun-17
Publisher
Monterey, California: Naval Postgraduate School
Language
Abstract
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.
Type
Thesis
Description
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
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.
Collections