Algorithms 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 cet article, nous proposons différents algorithmes pour la résolution approchée du problème du Sac-à-dos Multiple-Choix Multidimensionnel, MMKP, un problème NP-difficile. Le premier algorithme, nommé CP, est une approche constructive capable de produire une solution initiale en un temps très faible. Le deuxième algorithme est appliqué pour améliorer la qualité de la solution produite par CP. On le nommera CCP. Par la suite, nous proposons l'algorithme de pénalisation qui est basé sur une recherche locale de type recherche guidée. Cette approche est une procédure à deux phases : (i) la première phase est une phase de pénalisation d'une solution non améliorée et paraissant être bloquée autour d'un optimum local, ensuite, (ii) la seconde phase est appliquée pour normaliser la configuration de la solution pénalisée et de l'améliorer. La performance de ces approches est évaluée sur un ensemble d'instances extraites de la littérature, et comparée aux résultats obtenus par d'autres approches déjà publiées.
Mots clés : Optimisation combinatoire, recherche locale guidée, heuristique, sac-à-dos.

Abstract. In this paper, we propose several algorithms for approximately solving the Multiple-Choice Multi-dimensional Knapsack Problem (noted MMKP), an NP-Hard combinatorial optimization problem. The first algorithm is a constructive approach used especially for constructing an initial feasible solution for the problem. The second approach is applied in order to improve the quality of the initial solution. Finally, we introduce the main algorithm which starts by applying the first approach and tries to produce a better solution to the MMKP. The last approach can be viewed as a two-stage procedure : (i) the first-stage is applied in order to penalize a chosen feasible solution and (ii) the second-stage is used in order to normalize and to improve the solution given by the first-stage. The performance of the proposed approaches has been evaluated on problem instances extracted from the literature. Encouraging results have been obtained.
Keywords : Combinatorial optimization, guided local search, heuristic, knapsack.

JEL Classification : C44, C61, C63.

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