[Back]

J. Puchinger, G. Raidl, U. Pferschy:
"The multidimensional knapsack problem: Structure and algorithms";
Informs Journal on Computing, 22 (2010), 2; 250 - 265.

We study the multidimensional knapsack problem, present some theoretical and empirical results about its
structure, and evaluate different integer linear programming (ILP)-based, metaheuristic, and collaborative
approaches for it. We start by considering the distances between optimal solutions to the LP relaxation and the
original problem and then introduce a new core concept for the multidimensional knapsack problem (MKP),
which we study extensively. The empirical analysis is then used to develop new concepts for solving the
MKP using ILP-based and memetic algorithms. Different collaborative combinations of the presented methods
are discussed and evaluated. Further computational experiments with longer run times are also performed to
compare the solutions of our approaches to the best-known solutions of another so-far leading approach for
common MKP benchmark instances. The extensive computational experiments show the effectiveness of the
proposed methods, which yield highly competitive results in significantly shorter run times than do previously
described approaches.