The Core Concept for the Multidimensional Knapsack Problem

International audienceWe present the newly developed core concept for the Mul-tidimensional Knapsack Problem (MKP) which is an extension of the classical concept for the one-dimensional case. The core for the mul-tidimensional problem is defined in dependence of a chosen efficiency function of the items, since no single obvious efficiency measure is available for MKP. An empirical study on the cores of widely-used benchmark instances is presented, as well as experiments with different approximate core sizes. Furthermore we describe a memetic algorithm and a relaxation guided variable neighborhood search for the MKP, which are applied to the original and to the core problems. The experimental results show that given a fixed run-time, the different metaheuristics as well as a general purpose integer linear programming solver yield better solution when applied to approximate core problems of fixed size