programmation par contraintes

La programmation par contraintes (PPC, ou CP pour constraint programming en anglais) est un paradigme de programmation apparu dans les années 1970 et 1980 permettant de résoudre des problèmes combinatoires de grande taille tels que les problèmes de planification et d'ordonnancement. En programmation par contraintes, on sépare la partie modélisation à l'aide de problèmes de satisfaction de contraintes (ou CSP pour Constraint Satisfaction Problem), de la partie résolution dont la particularité réside dans l'utilisation active des contraintes du problème pour réduire la taille de l'espace des solutions à parcourir (on parle de propagation de contraintes). « En informatique, de toutes les approches en programmation, la programmation par contraintes se rapproche le plus de l'idéal : l'utilisateur décrit le problème, l'ordinateur le résout. » — E. Freuder Dans le cadre de la programmation par contraintes, les problèmes sont modélisés à l'aide de variables de décision et de contraintes, où une contrainte est une relation entre une ou plusieurs variables qui limite les valeurs que peuvent prendre simultanément chacune des variables liées par la contrainte. Les algorithmes de recherche de solution, en PPC, s'appuient généralement sur la propagation de contraintes, pour réduire le nombre de solutions candidates à explorer, ainsi que sur une recherche systématique parmi les différentes affectations possibles de chacune des variables. De tels algorithmes garantissent de trouver une solution, quand elle existe, et permettent de prouver qu'il n'existe pas de solution à un problème s'ils n'ont pas trouvé de solution à la fin de la recherche exhaustive. Un des premiers solveur de contraintes est ALICE écrit en 1976 par Jean-Louis Laurière.