Publication: Greedy algorithm for the general multidimensional knapsack problem
Program
KU-Authors
KU Authors
Co-Authors
Li, Haijun
Xu, Susan H.
Publication Date
Language
Type
Embargo Status
Journal Title
Journal ISSN
Volume Title
Alternative Title
Abstract
In this paper, we propose a new greedy-like heuristic method, which is primarily intended for the general MDKP, but proves itself effective also for the 0-1 MDKP. Our heuristic differs from the existing greedy-like heuristics in two aspects. First, existing heuristics rely on each item's aggregate consumption of resources to make item selection decisions, whereas our heuristic uses the effective capacity, defined as the maximum number of copies of an item that can be accepted if the entire knapsack were to be used for that item alone, as the criterion to make item selection decisions. Second, other methods increment the value of each decision variable only by one unit, whereas our heuristic adds decision variables to the solution in batches and consequently improves computational efficiency significantly for large-scale problems. We demonstrate that the new heuristic significantly improves computational efficiency of the existing methods and generates robust and near-optimal solutions. The new heuristic proves especially efficient for high dimensional knapsack problems with small-to-moderate numbers of decision variables, usually considered as "hard" MDKP and no computationally efficient heuristic is available to treat such problems.
Source
Publisher
Springer
Subject
Operations research, Management science
Citation
Has Part
Source
Annals of Operations Research
Book Series Title
Edition
DOI
10.1007/s10479-006-0150-4