Propagation de contraintes

La propagation de contraintes dans le domaine de la programmation par contraintes est le fait de réduire le domaine d'une variable afin de maintenir l'ensemble des valeurs possibles cohérent avec les contraintes du problème. La propagation de contraintes permet ainsi de résoudre un problème si la propagation permet d'établir la cohérence du problème. Les techniques de propagation de contraintes sont utilisées pour réduire la taille de l'espace de recherche lors de la résolution d'un problème de satisfaction de contraintes par un algorithme de recherche arborescente.

Cohérence d'arcs (arc consistency)

La propagation de contraintes consiste à modifier (i.e. réduire) le domaine des variables impliquées dans une contrainte, dans le but de rétablir la cohérence. Plusieurs types de cohérences, plus ou moins fortes peuvent être considérées.

La cohérence d'arcs est définie ainsi :

• Une contrainte binaire $C(x,y)$ est cohérente par arc (abrégé en AC pour arc consistent) si pour toute valeur du domaine de $x$, il existe au moins une valeur du domaine de $y$ telle que la contrainte soit satisfaite, et vice-versa. La description symbolique de la cohérence par arc d'une contrainte est :
  $$AC(C_{x,y})=\forall x_{i}\in D_{x},\exists y_{j}\in D_{y},C_{x,y}(x_{i},y_{j})$$
  où $D_{x}$ et $D_{y}$désignent respectivement les domaines de $x$ et de $y$.
• La cohérence d'arcs d'un problème est satisfaite si chaque contrainte binaire est cohérente par arc.

Une généralisation de la cohérence d'arcs pour les contraintes sur plus de deux variables est décrite en termes de cohérence d'hyperarcs ou cohérence d'arcs généralisée.

Exemple

Soit le CSP ${\mathcal {P}}$ défini par les variables $x,y,z\in \{1,2\}$ avec les contraintes suivantes :

• $x\neq y$ $(c_{1})$
• $y\neq z$ $(c_{2})$
• $x\neq z$ $(c_{3})$

Pour chacune des valeurs du domaine de $x$, il existe une valeur du domaine de $y$ qui satisfait la contrainte $c_{1}$. En effet, pour $x=1$ (resp. $2$), l'instanciation $y=2$ (resp. $1$) satisfait la contrainte $c_{1}$. La contrainte $c_{1}$ est donc cohérente par arc. De la même façon $c_{2}$ et $c_{3}$ sont cohérentes par arc.

On s'aperçoit ainsi qu'il ne suffit pas qu'un problème soit AC pour admettre une solution. Ce point est en fait fondamental : on peut montrer que les algorithmes de rétablissement de la cohérence par arcs (dans le cas des contraintes binaires) ont une complexité temporelle polynomiale, alors qu'en règle générale, les algorithmes de rétablissement de la cohérence complète ont une complexité temporelle exponentielle.

AC3

• Soit la contrainte $C_{i,j}$
• $x$ parcourant toutes les valeurs possibles de la première variable $V_{i}$
• $y$ parcourant toutes les valeurs possibles de la seconde variable $V_{j}$
• Si, pour un $x$ donné, $(x,y)$ viole $C_{i,j}$ pour toutes les valeurs $y$ de la variable $V_{j}$, alors enlever $x$ du domaine de la variable $V_{i}$.
• Si une valeur $x$ a été enlevée de $V_{i}$, répéter ces vérifications pour toutes les contraintes impliquant la variable $V_{i}$

Cet algorithme nécessite donc de gérer une pile comprenant les variables dont le domaine est modifié.

On peut montrer que si $m$ est la taille maxi des domaines des variables et $n$ le nombre de contraintes, alors :

• Une contrainte $C_{i,j}$ est examinée au plus $m$ fois (car une contrainte est examinée à cause de la suppression d'une valeur dans le domaine de sa première variable, et qu'on ne peut pas supprimer plus de $m$ valeurs du domaine).
• Il y a donc au plus $m\times n$ examens de contraintes
• Chaque examen de contrainte nécessite $m^{2}$ vérifications.
• L'algorithme a donc une complexité en $O(nm^{3})$.

AC2001

Cet algorithme est une optimisation de AC3. Dans AC3, le fait de faire parcourir tout le domaine de $V_{i}$ par x est inefficace lors de l'examen d'une contrainte qui a déjà été examinée. Si dans une étape précédente, la vérification a déjà été faite pour une valeur x et qu'elle n'a pas trouvé de violation, il est intéressant de conserver cette information. Lors d'une vérification ultérieure, il faut commencer la vérification par la valeur suivante de $V_{i}$.

On peut montrer que cet algorithme a une complexité temporelle en $O(nm^{2})$ dans le pire des cas et une complexité spatiale en $O(nm)$. Ça en fait l'algorithme le plus performant à l'heure actuelle.

Utilisation de la sémantique de la contrainte

Les algorithmes AC3 ou AC2001 sont adaptés aux contraintes qui ne sont définies que par la donnée des valeurs violant la contrainte. Cependant dans la majorité des problèmes concrets à résoudre, les contraintes sont définies par une expression symbolique : on définit une contrainte de différence sur [1..3] × [1..2] par $V_{1}\neq V_{2}$ plutôt que par la donnée des couples interdits : (1,1) et (2,2) et des couples autorisés : (1,2) (1,3) (2,1) (3,1).

Exemples —  Pour une telle contrainte de différence, un algorithme extrêmement simple consiste à supprimer $x$ du domaine de $V_{2}$ uniquement lorsque le domaine de $V_{1}$ a été réduit au singleton $\{x\}$.

Pour des contraintes de type $V_{1}\leq V_{2}$, la propagation de contrainte efficace consiste à ne considérer que les bornes des domaines des variables : si la borne supérieure de $V_{2}$ a diminué, il faut diminuer celle de $V_{1}$ en conséquence. Mais si c'est la borne inférieure de $V_{2}$ qui a augmenté, alors il n'y a pas de propagation à faire, car la contrainte ne permet pas de déduire une nouvelle information sur $V_{1}$.

Pour la contrainte d'égalité, la propagation consiste à conserver les domaines des deux variables totalement identiques.

En pratique, les systèmes de résolution des problèmes de PPC offrent par défaut un algorithme de type AC3 ou AC2001 pour les contraintes définies par des ensembles de valeurs permises et interdites (contraintes tabulaires), et une bibliothèque de contraintes particulières fournies avec leur algorithme efficace de propagation. De tels systèmes offrent également le moyen de combiner des contraintes entre elles et de les propager efficacement (par exemple : Et(C1,C2) se propage en propageant à la fois C1 et C2 ; Ou(C1,C2) se propage en ne propageant C2 que lorsqu'il devient certain que C1 ne sera pas satisfaite et réciproquement).

Cohérence de nœud

Elle consiste à ne considérer qu'une seule variable. On retire alors toutes les valeurs pour lesquelles au moins une contrainte est impossible à satisfaire. Ce filtrage est très rapide, mais peu efficace (étant donné qu'on ne considère aucune autre variable impliquée dans la contrainte).

Cohérence d'hyperarcs

Aussi appelée hyperarc consistency (HAC), c'est une généralisation de la cohérence d'arcs pour les contraintes non binaires. Elle a aussi été appelée cohérence d'arcs généralisée (GAC). Le principe est le même que pour les contraintes binaires : une contrainte est HAC si et seulement si chaque valeur de chaque variable appartient à une solution de la contrainte. On établit la cohérence d'hyperarcs en supprimant toutes les valeurs qui ne satisfont pas cette propriété.

Par exemple, la contrainte Alldiff implique que les variables sur lesquelles elle est définie prennent des valeurs deux à deux différentes. On sait établir efficacement la cohérence par hyperarc de cette contrainte.

k-cohérence

Elle consiste à considérer $k$ variables, et à tester tous les $k$-uplets de valeurs possibles afin de tester s'ils ne violent pas les contraintes. Plus $k$ est grand, plus le filtrage sera efficace. Cependant, du fait du grand nombre de combinaisons à tester, cela reste souvent trop lourd. La 3-cohérence donne de bons résultats, cependant du fait de la complexité de son implémentation, elle n'est que très rarement présente dans des solveurs de contraintes.

La 2-cohérence est en fait une autre expression de la cohérence d'arcs. Si un problème contient $n$ variables, alors la $n$-cohérence consisterait à tester l'ensemble des possibilités.

Cohérence de bornes

Lorsque les domaines des variables sont trop grands (plusieurs milliers d'éléments), le fait de stocker l'appartenance ou non de chaque valeur au domaine de la variable peut se révéler trop lourd à traiter. On utilise dans ce cas la consistance de bornes, qui consiste à simplement raisonner sur les valeurs minimum et maximum que les variables peuvent prendre. Pour certaines contraintes, comme par exemple celles d'inégalités ($X<Y$), la cohérence de bornes est très proche, voire équivalente, à la cohérence d'arcs.