Propagation de contraintes - Définition

Dans les algorithmes de programmation par contraintes, la propagation de contraintes permet de réduire les domaines des variables, dans le but d'accélérer le parcours de l'arbre de recherche.

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

Le problème suivant :

• x ∈ [1..2]
• y ∈ [1..2]
• z ∈ [1..2]

• C1 : x ≠ y
• C2 : y ≠ z
• C3 : x ≠ z

Est AC, car chacune de ses contraintes C1, C2, ou C3 est AC. En effet, si x=1, alors y=2 et z=2 sont des valeurs qui respectent toutes les contraintes. De même si x=2, alors y=1 et z=1 respectent toutes les contraintes.

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) sont de complexité polynomiale, alors qu'en règle générale, le rétablissement de la consistance complète est de complexité exponentielle.

Autres notions de consistance

La notion de consistance par arcs peut se généraliser : consistance par chemins par exemple.

On peut aussi considérer, lorsque les domaines sont des ensembles finis d'entiers, la consistance de bornes. Elle consiste à n'assurer l'AC que sur les bornes des domaines des variables. Ce type de consistance est particulièrement adapté aux contraintes linéaires avec les opérateurs de comparaison =, < ou ≠ .

Algorithmes AC

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 (x,y) viole la contrainte, alors enlever y du domaine de la variable V_j
• Répéter ces vérifications pour toutes les contraintes impliquant la variable V_j

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 seconde 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_j par y est inefficace. Si dans une étape précédente, la vérification a déjà été faite pour une valeur y 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 cette valeur y.

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

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éfault un algorithme de type AC3 ou AC2001 pour les contraintes définies par des ensembles de valeurs permises et interdites (contraintes tablulaires), 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).