La programmation par contrainte

La programmation par contraintes (PPC, ou CP pour Constraint Programming en anglais) consiste à poser un problème sous forme de relations logiques (appelées contraintes) entre plusieurs variables. Un problème formulé de la sorte comporte donc un certain nombre de ces variables, chacune ayant un domaine (i.e. un ensemble de valeur possibles), et un certain nombre de contraintes. Le domaine d'une variable peut être fini (intervalle de nombres entiers, intervalle d'ensembles par exemple) ou continu.

Une contrainte implique une ou plusieurs variables, et restreint les valeurs que peuvent prendre simultanément ces variables. Lorsqu'une contrainte implique deux (respectivement n) variables, on parle de contrainte binaire (respectivement n-aire). Lorsqu'elle implique un nombre non fixé de variables, on parle de contrainte globale.

Trouver une solution à un problème de PPC consiste à décider s'il existe ou non une affectation de toutes les variables telle que l'ensemble des contraintes du problème soient satisfaites.