TITLE:
The 0/1 Multidimensional Knapsack Problem and Its Variants: A Survey of Practical Models and Heuristic Approaches
AUTHORS:
Soukaina Laabadi, Mohamed Naimi, Hassan El Amri, Boujemâa Achchab
KEYWORDS:
0/1 Multidimensional Knapsack Problem, Survey, Real-World Applications, Heuristics, Metaheuristics
JOURNAL NAME:
American Journal of Operations Research,
Vol.8 No.5,
September
30,
2018
ABSTRACT: The 0/1 Multidimensional Knapsack Problem (0/1 MKP) is an interesting
NP-hard combinatorial optimization problem that can model a number of
challenging applications in logistics, finance, telecommunications and other
fields. 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 dimensions
having each a limited capacity. The goal is to find a subset of items
leading 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 a
little number of recent review papers on this problem. Furthermore, the existing
reviews focus particularly on some specific issues. This paper aims to
give a general and comprehensive survey of the considered problem so that it
can be useful for both researchers and practitioners. Indeed, we first describe
the 0/1 MKP and its relevant variants. Then, we present the detailed models
of some important real-world applications of this problem. Moreover, an
important collection of recently published heuristics and metaheuristics is
categorized and briefly reviewed. These approaches are then quantitatively
compared through some indicative statistics. Finally, some synthetic remarks
and research directions are highlighted in the conclusion.