eduzhai > Physical Sciences > Physics Sciences >

The 0/1 Multidimensional Knapsack Problem and Its Variants: A Survey of Practical Models and Heuristic Approaches

  • Save

... pages left unread,continue reading

Document pages: 45 pages

Abstract: The 0 1 Multidimensional Knapsack Problem (0 1 MKP) is an interestingNP-hard combinatorial optimization problem that can model a number ofchallenging applications in logistics, finance, telecommunications and otherfields. In the 0 1 MKP, a set of items is given, each with a size and value,which has to be placed into a knapsack that has a certain number of dimensionshaving each a limited capacity. The goal is to find a subset of itemsleading to the maximum total profit while respecting the capacity constraints.Even though the 0 1 MKP is well studied in the literature, we can just find alittle number of recent review papers on this problem. Furthermore, the existingreviews focus particularly on some specific issues. This paper aims togive a general and comprehensive survey of the considered problem so that itcan be useful for both researchers and practitioners. Indeed, we first describethe 0 1 MKP and its relevant variants. Then, we present the detailed modelsof some important real-world applications of this problem. Moreover, animportant collection of recently published heuristics and metaheuristics iscategorized and briefly reviewed. These approaches are then quantitativelycompared through some indicative statistics. Finally, some synthetic remarksand research directions are highlighted in the conclusion.

Please select stars to rate!


0 comments Sign in to leave a comment.

    Data loading, please wait...