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 contrainte afin de maintenir l'ensemble de valeur possible 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.

Consistance par arcs

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 consistance. Plusieurs types de consistances, plus ou moins fortes peuvent être considérées.

La consistance par arcs est définie ainsi :

• Une contrainte binaire C(x, y) est consistante par arcs (AC) 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.
• Une contrainte à plus de deux variables C(x, y, ..., t) est AC si pour toute variable v impliquée dans la contrainte, et pour toute valeur du domaine de v, il existe au moins une valeur dans le domaine de chaque autre variable impliquée telle que la contrainte soit satisfaite. On parle alors de consistance par arcs généralisée (GAC).
• Un problème est AC si toutes ses contraintes sont AC

Une définition plus mathématique : AC(C_{i, j}) = ∀x ∃y ( x ∈ D_i ∧ y ∈ D_j ∧ C_{i, j}(x, y) )

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₁)
• $y \neq z$ (c₂)
• $x \neq z$ (c₂)

Pour chacune des valeurs du domaine de x il existe une valeur du domaine de y qui satisfait la contrainte c₁, effet pour x = 1 (resp. 2), l'instanciation y = 2 (resp. 1) satisfait la contrainte c₁, la contrainte c₁ est donc arc consistant; de la même façon c₂ et c₃ sont arc consistant.

On s'aperçoit ainsi qu'un problème AC n'est pas totalement consistant, puisque ce problème n'admet pas de solution. Ce point est en fait fondamental : on peut montrer que les algorithmes de rétablissement de la consistance 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 consistance 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 × n) examen de contraintes
• Chaque examen de contrainte nécessite m² vérifications.
• L'algorithme a donc une complexité en O( n · m³ )

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é en O( n · m² ), et qu'il est optimal.

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₁ ≠ V₂ plutôt que par la donnée des couples interdits : (1,1) et (2,2) et des couples autorisés : (1,2) (2,1) (3,1).

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

Pour des contraintes de type V₁ ≤ V₂, la propagation de contrainte efficace consiste à ne considérer que les bornes des domaines des variables : si la borne supérieure de V₂ a diminué, il faut diminuer celle de V₁ en conséquence. Mais si c'est la borne inférieure de V₂ 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₁.

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 lorsque il devient certain que C1 ne sera pas satisfaite et réciproquement).

Consistance 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).

Consistance d'hyperarc

Aussi appelée Hyperarc Consistency (HAC), c'est une généralisation de la consistance d'arc pour les contraintes non binaires. Elle a aussi été appelée consistance d'arc généralisée. 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 consistance d'hyperarc en supprimant toutes les valeurs qui ne satisfont pas cette propriété.

Par exemple, la contrainte Alldiff impliquent que les variables sur lesquelles elle est définie prennent des valeurs deux à deux différentes. On sait établir efficacement la consistance d'hyperarc pour cette contrainte.

k-consistance

Elle consiste à considérer k variables, et de 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-consistance 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-consistance est en fait une autre vue de la consistance d'arc. Si un problème contient n variables, alors la n-consistance consisterait à tester l'ensemble des possibilités.

Consistance 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é ( X < Y ), la consistance de bornes est très proche, voire équivalente, à la consistance d'arc.

Notes et références