Developing New Multidimensional Knapsack Heuristics Based on Empirical Analysis of Legacy Heuristics

摘要

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 of test problem characteristics. This work first employs an available, robust set of two-dimensional knapsack problems in an empirical study to garner performance insights. These performance insights are tested against a larger set of problems, five-dimensional knapsack problems specifically generated for empirical testing purposes. The performance insights are found to hold in the higher dimensions. These insights are used to formulate and test a suite of three new greedy heuristics for the MKP, each improving upon its successor. These heuristics are found to outperform available legacy heuristics across a complete spectrum of test problems. Problem reduction heuristics are examined and the subsequent performance insights garnered are used to derive a new problem reduction heuristic, which is then further extended to employ a local improvement phase. These problem reduction heuristics are also found to outperform currently available approaches. Available problem test sets are shown lacking along multiple dimensions of importance for viable empirical testing.