A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem

In this paper, we approximately solve the multiple-choice multi-dimensional knapsack problem. We propose an algorithm which is based upon reactive local search and where an explicit check for the repetition of configurations is added to the local search. The algorithm starts by an initial solution and is improved by using a fast iterative procedure. Later, both deblocking and degrading procedures are introduced in order (i) to escape to local optima and, (ii) to introduce diversification in the search space. Finally, a memory list is applied in order to forbid the repetition of configurations. The performance of the proposed approaches has been evaluated on several problem instances. Encouraging results have been obtained.