Greedy algorithm for the general multidimensional knapsack problem |
| |
Authors: | Yalçın Akçay Haijun Li Susan H Xu |
| |
Institution: | 1.College of Administrative Sciences and Economics,Ko? University,Istanbul,Turkey;2.Department of Mathematics,Washington State University,Pullman,USA;3.Department of Supply Chain and Information Systems, The Smeal College of Business Administration,The Pennsylvania State University,Pennsylvania,USA |
| |
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.
Supported in part by the NSF grant DMI 9812994. |
| |
Keywords: | Integer programming Multidimensional knapsack problems Heuristics |
本文献已被 SpringerLink 等数据库收录! |
|