A best first search exact algorithm for the Multiple-choice Multidimensional Knapsack Problem

In this paper, we propose an optimal algorithm for the Multiple-choice Multidimensional Knapsack Problem MMKP. The main principle of the approach is twofold: (i) to generate an initial feasible solution as a starting lower bound, and (ii) at different levels of the search tree to determine an intermediate upper bound obtained by solving an auxiliary problem called MMKPaux and perform the strategy of fixing items during the exploration. The approach which we develop is of best-first search strategy. The method was able to optimally solve the MMKP. The performance of the exact algorithm is evaluated on a set of small and medium instances, some of them are extracted from the literature and others are randomly generated. This algorithm is parallelizable and this is one of its important features.