Utilisateur:PierreSelim/PPC

La programmation par contraintes (PPC, ou CP pour Constraint Programming en anglais) est un paradigme de programmation apparu dans les années 80 permettant de résoudre des problèmes combinatoires de grandes tailles tels que les problèmes de planification et d'ordonnancement. La programmation par contraintes sépare la partie modélisation à l'aide de problème de satisfaction de contraintes, 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).

« Constraint Programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it. »

— E. Freuder

Dans le cadre de la PPC, les problèmes sont modélisés sous à 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 affectation possible 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 CSP si ils n'ont pas trouvé de solutions à la fin de la recherche exhaustive.

Problème de satisfaction de contraintes sur les domaines finis

Une contrainte est une relation entre plusieurs varaibles qui limitent l'ensemble des valeurs que peuvent prendre ces variables simultanément.

Définition — Un problème de satisfaction de contraintes sur des domaines finis (ou CSP) est défini par un triplet $({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ où:

• ${\mathcal {X}}=\{x_{1},\dots ,x_{n}\}$ est l'ensemble de variables du problème;
• ${\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}$ est l'ensemble des domaines des variables, c'est-à-dire que pour tout $k\in [1;n]$ on a $x_{k}\in {\mathcal {D}}_{k}$;
• ${\mathcal {C}}=\{C_{1},\dots ,C_{m}\}$ est un ensemble de contraintes. Une contrainte $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ est définie par l'ensemble ${\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}$ des variables sur lequel elle porte et la relation ${\mathcal {R}}_{i}\subset {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}$ qui définie l'ensemble des valeurs que peuvent prendre simultéanément les variables de ${\mathcal {X}}_{i}$:

On appelle affectation, le fait d'associer une valeur de son domaine à une variable. Dans le cadre de la résolution de problème de satisfaction de contraintes, on parle d'affectation partielle lorsque l'on affecte un sous-ensemble de l'ensemble des variables du problème, et d'affectation totale lorsque l'on affecte toutes les variables du problème.

Définition —  Une affectation ${\mathcal {A}}$ d'un CSP $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ est définie par le couple ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ où:

• ${\mathcal {X_{\mathcal {A}}}}\subset {\mathcal {X}}$ est un sous-ensemble de variables;
• ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ est le tuple des valeurs prises par les variables affectées.

On dit qu'une affectation est partielle lorsque l'ensemble de variables affectées est différent de l'ensemble des variables du problème, sinon on parle d'affectation totale.

Propriété — Soit ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ une affectation (partielle ou totale) d'un CSP $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$, et $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ une contrainte de $P$ tel que ${\mathcal {X}}_{i}\subset {\mathcal {X_{\mathcal {A}}}}$, l'affectation ${\mathcal {A}}$ satisfait la contrainte $C_{i}$ si et seulement si l'ensemble des valeurs ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ des variables sur lesquelles porte la contrainte $C_{i}$ appartient à ${\mathcal {R}}_{i}$.

Définition — Une solution d'un CSP est une affectation totale qui satisfait l'ensemble des contraintes.

Notes et références

• (en) Intro CP