Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Engineering
Empirical Analysis Of Various Multi-Dimensional Knapsack Heuristics, Yong Kun Cho
Empirical Analysis Of Various Multi-Dimensional Knapsack Heuristics, Yong Kun Cho
Theses and Dissertations
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 research is to explore which heuristic of the three representative greedy heuristics performs best under …