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

Mhand Hifi*, LaRIA et CERMSEM
Mustapha Michrafi*, LaRIA et CERMSEM
Abdelkader Sbihi*, LaRIA et CERMSEM

Résumé. Dans le présent article, nous nous intéressons au problème du Sac-à-Dos Multiple-Choix Multidimensionnel en variables bivalentes, MMKP, et nous proposons de le résoudre approximativement. L'heuristique proposée est basée sur une recherche locale réactive où la répétition des configurations des solutions obtenues est mise tabou au cours de la recherche. L'algorithme démarre par une solution initiale admissible et améliorée par une procédure itérative rapide. Ensuite, les stratégies débloquer et dégrader une solution courante sont introduites pour : (i) échapper à un optimum local, (ii) introduire une diversification de la recherche dans l'espace admissible de recherche. Enfin, une liste dite liste mémoire est utilisée pour interdire toute répétition dans les configurations des solutions déjà visitées. Les résultats obtenus sont encourageants et permettent d'obtenir des solutions de très bonne qualité et consommant un temps d'exécution raisonnable. L'algorithme de recherche locale réactive est facilement parallélisable, ce qui constitue l'un des intérêts à explorer dans des travaux en perspective.
Mots clés : Optimisation combinatoire, heuristique, problèmes du Sac-à-Dos, recherche locale réactive, recherche tabou.

Abstract. In this paper, we approximately solve the multiple-choice multi-dimensional knapsack problem. We propose an algorithm which is based upon the reactive local search and where an explicit check for repetition of configurations is added to the local search. The algorithm starts by an initial feasible solution and improved by using a fast iterative procedure. Later, both unblocking and degrading procedures are introduced in order : (i) to escape to local optima and, (ii) to introduce diversification to the feasible search space. Finally, a memory list is introduced in order to forbid the repetition of configurations. The computational results show that the proposed algorithm produces high-quality solutions within reasonable computational times. The reactive local search-based algorithm is easily parallelizable ; one of its important features to be investigated in the near future.
Keywords : Combinatorial optimization, heuristics, knapsack problems, reactive local search, tabu search.

JEL Classification : C44, C61, C63.

*LaRIA, Laboratoire de Recherche en Informatique d'Amiens, 5 rue du Moulin Neuf, 80000 Amiens, France.