Paper Info
Title
Fast, effective heuristics for the 0-1 multi-dimensional knapsack problem
Abstract
The objective of the multi-dimensional knapsack problem (MKP) is to find a subset of items with maximum value that satisfies a number of knapsack constraints. Solution methods for MKP, both heuristic and exact, have been researched for several decades. This paper introduces several fast and effective heuristics for MKP that are based on solving the LP relaxation of the problem. Improving procedures are proposed to strengthen the results of these heuristics. Additionally, the heuristics are run with appropriate deterministic or randomly generated constraints imposed on the linear relaxation that allow generating a number of good solutions. All algorithms are tested experimentally on a widely used set of benchmark problem instances to show that they compare favourably with the best-performing heuristics available in the literature.
Year
DOI
Venue
2009
10.1016/j.cor.2008.03.003
Computers & OR
Keywords
DocType
Volume
Multi-dimensional knapsack problem,linear relaxation,Heuristics,appropriate deterministic,benchmark problem instance,best-performing heuristics,good solution,knapsack constraint,multi-dimensional knapsack problem,LP relaxation,Improving procedure,effective heuristics
Journal
36
Issue
ISSN
Citations 
5
Computers and Operations Research
17
PageRank 
References 
Authors
0.75
14
2
Name
Order
Citations
PageRank
Krzysztof Fleszar136825.38
Khalil S. Hindi239822.75