Problem reduction heuristic for the 0–1 multidimensional knapsack problem

Problem reduction heuristic for the 0–1 multidimensional knapsack problem

0.00 Avg rating0 Votes
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: , ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.