Article ID: | iaor20115795 |
Volume: | 39 |
Issue: | 1 |
Start Page Number: | 19 |
End Page Number: | 26 |
Publication Date: | Jan 2012 |
Journal: | Computers and Operations Research |
Authors: | Hill Raymond R, Kun Cho Yong, Moore James T |
Keywords: | heuristics |
This paper introduces new problem‐size reduction heuristics for the multidimensional knapsack problem. These heuristics are based on solving a relaxed version of the problem, using the dual variables to formulate a Lagrangian relaxation of the original problem, and then solving an estimated core problem to achieve a heuristic solution to the original problem. We demonstrate the performance of these heuristics as compared to legacy heuristics and two other problem reduction heuristics for the multi‐dimensional knapsack problem. We discuss problems with existing test problems and discuss the use of an improved test problem generation approach. We use a competitive test to highlight the performance of our heuristics versus the legacy heuristic approaches. We also introduce the concept of computational versus competitive problem test data sets as a means to focus the empirical analysis of heuristic performance.