Groupe d’études et de recherche en analyse des décisions

Le problème du sac-à-dos multidimensionnel en variables 0-1

Saïd Hanafi

Le problème du sac-à-dos multidimensionnel en variables 0-1 est l'un des modèles d'allocation de ressources les plus connus parmi les problèmes de programmation en nombres entiers. Dans les 10 dernières années, une quantité impressionnante d'articles ont été publiés sur le sujet et des méthodes efficaces sont disponibles pour résoudre de très grandes instances. Pendant ce temps, la communauté de la recherche opérationnelle a porté une attention moindre au cas multidimensionnel.

Bien que des avancées récentes ont rendu possible la résolution d'instances de taille moyenne, la résolution de ce problème NP difficile reste un défi très intéressant, en particulier lorsque le nombre de contraintes augmente. Cet exposé recense les principaux résultats en termes à la fois de propriétés théoriques et de solutions approchées publiés dans la littérature concernant les méthodes basées sur la dualité surrogate et composite et sur les métaheuristiques efficaces.