Date of Award
3-2002
Document Type
Thesis
Degree Name
Master of Science
Department
Department of Operational Sciences
First Advisor
Raymond R. Hill, PhD
Abstract
Since the multidimensional knapsack problems are NP-hard problems, the exact solutions of knapsack problems often need excessive computing time and storage space. Thus, heuristic approaches are more practical for multidimensional knapsack problems as problems get large. This thesis presents the results of an empirical study of the performance of heuristic solution procedures based on the coefficients correlation structures and constraint slackness settings. In this thesis, the three representative greedy heuristics, Toyoda, Senju and Toyoda, and Loulou and Michaelides methods, are studied. The purpose of this thesis is to explore which heuristic of the three representative greedy heuristics perform best under certain combination of conditions between constraint slackness and correlation structures. This thesis examines three heuristics over 1120 problems which are all 2KPs with 100 variables created by four constraint slackness settings and 45 feasible correlation structures. Then we analyze why the best heuristic behaves as it does as a function of problem characteristic. The last chapter presents two new heuristics using knowledge gained in the study. When these new heuristics are competitively tested against the three original heuristics, the results show their better performances.
AFIT Designator
AFIT-GOR-ENS-02-05
DTIC Accession Number
ADA401808
Recommended Citation
Dougherty, Shane A., "An Examination of Latency and Degradation Issues in Unmanned Combat Aerial Vehicle Environments" (2002). Theses and Dissertations. 4512.
https://scholar.afit.edu/etd/4512