Publication:
Greedy algorithm for the general multidimensional knapsack problem

Placeholder

School / College / Institute

Program

KU Authors

Co-Authors

Li, Haijun
Xu, Susan H.

Publication Date

Language

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

item.page.datauri

Link

Rights

Copyrights Note

Endorsement

Review

Supplemented By

Referenced By

1

Views

0

Downloads

View PlumX Details