Présentation du cours de programmation
par contraintes
La programmation par contraintes
est un paradigme de programmation qui permet de résoudre de nombreux
problèmes combinatoires
de grande échelle, comme par exemple la planification d’actions ou
l’ordonnancement. Dans cette approche, une séparation est faite entre
un modèle
(un problème de satisfaction / optimisation de contraintes, une
contrainte
étant une relation logique entre variables) et l’algorithme de
résolution
commun, pour des problèmes représentés par des variables discrètes. Ce
cours
présente les bases de ce domaine (décomposition variables / domaines /
valeur,
heuristiques sur les variables / valeurs, contraintes globales) et se
focalise sur la modélisation et les algorithmes (retour-arrière,
branch-and-bound, consistance d'arc).
Des exercices de modélisation
avec un solveur de contraintes open source complètent le cours.
pmorignot (at) yahoo (dot) fr