A Computational Study of a Multiple-Choice Knapsack Algorithm

The results from the computational testing of an algorithm designed to solve large-scale multiple-choice knapsack problems are described. Data list structures, sorting techniques, and fathoming criteria are investigated. It is determined that considerable storage space can be eliminated from the original implementation of the algorithm without affecting execution time. Also the insertion of a heap sort in the algorithm does provide a substantial reduction in computing time when solving the larger problems. Theoretical results relating to the multiple-choice knapsack are presented.