A Core-Based Exact Algorithm for the Multidimensional Multiple Choice Knapsack Problem

In the multidimensional multiple choice knapsack problem (MMKP), items with nonnegative profits are partitioned into groups. Each item consumes a predefined nonnegative amount of a set of resources with given availability. The problem looks for a subset of items consisting of exactly one item for each group that maximizes the overall profit without violating the resource constraints. The MMKP is among the most complex problems in the knapsack family. In the literature, although a plethora of heuristic approaches have been proposed, very few exact methods can be found, and all of them work only on limited size instances. In this paper, we propose a new exact approach for the problem. The method exactly solves subproblems of increasing size by means of a recursive variable-fixing process until an optimality condition is satisfied. The algorithm has several properties. Memory requirement remains almost constant during computation, and the method is general enough to be easily adapted to other knapsack problems. Finally, it can be converted at no cost into a heuristic approach. We close to optimality 10 open benchmark instances and improve the best-known values for many of the remaining ones. Interesting enough, our algorithm is able to find, within three minutes, better solutions than the ones found by Gurobi in one hour.