Intro à la résolution de prob.

L’objectif de ce cours est, au travers de divers problèmes combinatoires, d’aborder les principaux aspects de la programmation par contrainte : modélisation de problèmes et résolution de problèmes.
Ce cours proposera une introduction à la modélisation par contraintes, basée sur différents types de variables de décision (principalement entiers bornés et booléens) et de contraintes (linéaire, non-linéaire, en extension ou intention, …). Suivra un rapide panorama des contraintes globales les plus fréquemment utilisées.
La partie résolution abordera le filtrage et la propagation de contraintes permettant de réduire l’espace de recherche, puis la recherche/énumération permettant de créer l’arbre de recherche.
Les CM seront illustrés par de nombreux exemples et étayés par des TD. La partie pratique consistera en un projet collaboratif qui débutera dès les premiers enseignements et finira par une soutenance et un rapport. Ce projet permettra de se former à des outils tels que PyCSP3 ou MiniZinc

― Savoir identifier les variables de décision et les contraintes d’un problème.
― Savoir modéliser un problème de différentes façons.
― Savoir comparer et analyser des modèles.
― Comprendre les algorithmes de résolution basés sur la propagation de contraintes.
― Savoir faire du filtrage de contraintes.
― Utiliser des outils existants pour la résolution de problèmes et plus spécialement pour la programmation par contraintes.