GRASP for set packing problems
DELORME ; GANDIBLEUX ; RODRIGUEZ
Type de document
COMMUNICATION AVEC ACTES INTERNATIONAL (ACTI)
Langue
anglais
Auteur
DELORME ; GANDIBLEUX ; RODRIGUEZ
Résumé / Abstract
Dans ce papier, nous décrivons deux implémentations de la métaheuristique GRASP (greedy randomized adaptative search procedure) pour la résolution du problème de set packing (SPP). L'une d'entre-elles est particularisée pour un problème de set packing à coûts unitaires décrivant un problème réel. Les principales caractéristiques de ce problème sont présentées et leur influence sur le fonctionnement de GRASP est commentée. Les résultats observés sur différentes instances du problème sont rapportés et comparés avec ceux obtenus avec le logiciel CPLEX. Enfin, plusieurs améliorations possibles sont évoquées.
