Méthodes hybrides et règles de branchement
en optimisation combinatoire
Les problèmes d'optimisation combinatoire (par exemple SAT, le problème de déterminer si une expression en forme normale conjonctive est satisfaisable ou non) ont été examinés par deux catégories de chercheurs : les chercheurs en programmation mathématique (considérée comme un domaine de la recherche opérationnelle) et les chercheurs en satisfaction de contraintes (considérée comme un domaine de l’intelligence artificielle). Ces deux catégories de chercheurs se sont rapprochées au cours des dernières années et un des buts de cet atelier est de susciter des échanges fructueux entre elles.
Les méthodes de l'optimisation combinatoire peuvent être classées (grosso modo) en méthodes heuristiques et méthodes exactes. Les algorithmes heuristiques tels que les algorithmes de recuit simulé, les algorithmes tabous et les algorithmes génétiques essaient de trouver rapidement de bonnes solutions (qui ne sont pas forcément des solutions optimales). Les algorithmes exacts, dont les solutions de départ sont souvent «heuristiques», utilisent en général une forme de séparation et évaluation progressive («branch-and-bound») pour trouver une solution optimale ; ils peuvent consommer beaucoup de temps. Les méthodes hybrides, qui sont apparues récemment, combinent des idées provenant de ces deux domaines. Un des thèmes de l’atelier sera la conception de nouveaux algorithmes hybrides.
L’atelier portera aussi sur les règles de branchement. Ces règles constituent un élément crucial des algorithmes de séparation et évaluation progressive et le choix d’une bonne règle peut améliorer de façon spectaculaire l’efficacité de ces algorithmes. Il reste beaucoup à faire pour concevoir de bonnes règles de branchement (voir «Ming Ouyang, How good are branching rules in DPLL?, Discrete Appl. Math. 89 (1998), no. 1-3, 281--286»). Nous proposons d’explorer entre autres voies : celle se fondant sur le «branchement fort» introduit dans Concorde (un logiciel pour le problème du commis-voyageur symétrique), ou encore celle utilisant des heuristiques «locales» telles que GSAT ou Walksat pour trouver des variables de branchement.
|