Le but de ce cours est de s'attaquer à la résolution de problèmes combinatoire difficiles que l'on trouve fréquemment dans divers domaines applicatifs comme par exemple la configuration de produits, la planification, la vérification de matériel et de logiciel ou encore la fouille de données.
Deux modèles d’expression et de résolution de problèmes sous contraintes seront particulièrement étudiés : les problèmes de satisfaction de contraintes (CSP) et le problème de la satisfiabilité propositionnelle (SAT). Pour chacun de ses problèmes, nous décrirons dans un premier temps le formalisme en montrant des exemples de modélisations de problèmes. Ces deux problèmes étant NP-Complets, nous donnerons un aperçu des classes polynomiales connues. Seront ensuite présentés les algorithmes ou solveurs actuels les plus efficaces tout en mettant en avant leurs points forts et leurs limites. Cette présentation sera précédée par un panorama de différents paradigmes de résolutions (algorithmes complets de type retour-arrière et algorithmes incomplets de type recherche locale). Nous aborderons aussi diverses extensions de ces deux modèles permettant par exemple de modéliser et de résoudre des problèmes d’optimisations ou encore d’énumération. Ce domaine de recherche a donnée lieu à une multitude d’outils de modélisation et de résolutions de problèmes sous contraintes qui seront présentés tout le long du cours : Sicstus/Gnu-Prolog, Choco, CPLEX, etc.
Ce cours s’appuie sur une équipe enseignante de l’axe de recherche du CRIL du même nom « Algorithmes pour l’Inférence et contraintes ». Il a donc pour objet de présenter les évolutions les plus récentes dans le domaine.
- Enseignant(e): Said Jabbour
- Enseignant(e): Lakhdar Sais