Constraint Programming


Ce (mini-)cours est enseigné aux étudiants de 3ème année "Pilotage des Systèmes Industriels" du Département Génie des Procédés et Informatique de l'Ecole Nationale Supérieure des Ingénieurs en Arts Chimiques et Technologiques (INP/A7).

Il présente les éléments fondamentaux pour le traitement des problèmes de décision sous contraintes et introduit ainsi la théorie des Problèmes de Satisfaction de Contraintes (CSP) et de la Programmation Par Contraintes (PPC).

On met l'accent sur le concept de contraintes pour la modélisation, la propagation et la résolution de problèmes présentant des incertitudes sur les données ou les conditions d'exécution de la décision.

Les problèmes d'ordonnancement servent de trame pour l'illustration des concepts présentés.

Contenu du cours :

  • Formalisme des problèmes de satisfaction de contraintes
  • Propagation des contraintes de temps (consistance d'arc et de chemin)
  • Propagation des contraintes de ressources (opérations locales, globales)
  • Algorithmes d'instanciation (backtrack chronologique, maintien de cohérence, recherche à divergence limitée, ...)
  • Systèmes de Programmation Par Contraintes