Problem reduction heuristic for the 0–1 multidimensional knapsack problem

Publication year: 2012
Source: Computers & Operations Research, Volume 39, Issue 1, January 2012, Pages 19-26

Raymond R., Hill , Yong, Kun Cho , James T., Moore

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…