La Programmation Par Contraintes (PPC) est un paradigme de programmation issu de la Programmation Logique qui permet de modéliser simplement de nombreux problèmes d’optimisation combinatoire, omniprésents dans l’industrie et les services, et de les résoudre efficacement.
Le cours présente tout d’abord le formalisme générique des Problèmes de Satisfaction de Contraintes (CSP) puis les algorithmes fondamentaux qui permettent de les résoudre de manière exacte : la cohérence d’arc (et de borne) ainsi que le Branch & Prune et le Branch & Bound associés aux stratégies classiques de résolution. La bibliothèque FaCiLe pour OCaml sert ensuite de support pour d’écrire la structure d’un programme en contraintes sur les domaines finis dans le cadre d’un langage généraliste de haut niveau, en détaillant la construction des buts de recherche (sous-but, récursivité, itérateurs, optimisation, stratégies…), les contraintes globales, la réification de contraintes, la création de contraintes utilisateur, etc. en analysant l’impact de la modélisation et de la prise en compte des symétries sur l’efficacité de la résolution.
[Mutualisé avec le cours du même nom de la 3e année ENAC]