Operations Research, Systems Engineering and Industrial Engineering Commons^™

Developing New Multidimensional Knapsack Heuristics Based On Empirical Analysis Of Legacy Heuristics, Yong Kun Cho

Theses and Dissertations

The multidimensional knapsack problem (MKP) has been used to model a variety of practical optimization and decision-making applications. Due to its combinatorial nature, heuristics are often employed to quickly find good solutions to MKPs. While there have been a variety of heuristics proposed for the MKP, and a plethora of empirical studies comparing the performance of these heuristics, little has been done to garner a deeper understanding of heuristic performance as a function of problem structure. This dissertation presents a research methodology, empirical and theoretical results explicitly aimed at gaining a deeper understanding of heuristic procedural performance as a function …