18 au 22 septembre 2006
Centre de recherches mathématiques
Organisateur: Vašek Chvátal (Concordia)
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. Nous proposons d’explorer deux voies : la première se fonde sur le «branchement fort» introduit dans Concorde (un logiciel pour le problème du commis-voyageur symétrique), et la deuxième utilise des heuristiques «locales» telles que GSAT ou Walksat pour trouver des variables de branchement.