PROGRAMMATION PAR CONTRAINTES

Aide à la Décision et Intelligence Artificielle

Ouali Abdelkader

Licence 3 au département Informatique

UFR des sciences
Université de Caen Normandie
Contenu du cours

1. Problèmes sous contraintes

2. Modélisation CSP

3. Algorithmes de résolution

A. Ouali Programmation Par Contraintes (PPC) 2 / 58

Fubuki

▶ Étant donné un ensemble de pions chacun portant un chiffre (à gauche), et une grille partiellement remplie de
chiffres (à droite)

▶ Objectif : disposer les pions dans la grille afin que la somme indiquée pour chaque ligne et chaque colonne
soit satisfaite

A. Ouali Programmation Par Contraintes (PPC) 3 / 58

Fubuki

▶ Étant donné un ensemble de pions chacun portant un chiffre (à gauche), et une grille partiellement remplie de
chiffres (à droite)

▶ Objectif : disposer les pions dans la grille afin que la somme indiquée pour chaque ligne et chaque colonne
soit satisfaite

A. Ouali Programmation Par Contraintes (PPC) 3 / 58

Fubuki

▶ Étant donné un ensemble de pions chacun portant un chiffre (à gauche), et une grille partiellement remplie de
chiffres (à droite)

▶ Objectif : disposer les pions dans la grille afin que la somme indiquée pour chaque ligne et chaque colonne
soit satisfaite

A. Ouali Programmation Par Contraintes (PPC) 3 / 58

Fubuki

▶ Étant donné un ensemble de pions chacun portant un chiffre (à gauche), et une grille partiellement remplie de
chiffres (à droite)

▶ Objectif : disposer les pions dans la grille afin que la somme indiquée pour chaque ligne et chaque colonne
soit satisfaite

A. Ouali Programmation Par Contraintes (PPC) 3 / 58

Intérêt

En général, nous avons de nombreux problèmes (e.g. affectation, planification, sélection, etc.) dans différents
domaines (location, transport, recherche médicale, etc.) dont on :

▶ doit satisfaire un ensemble de contraintes

▶ avec des approches de résolution souvent communes

A. Ouali Programmation Par Contraintes (PPC) 4 / 58

Intérêt

En général, nous avons de nombreux problèmes (e.g. affectation, planification, sélection, etc.) dans différents
domaines (location, transport, recherche médicale, etc.) dont on :

▶ doit satisfaire un ensemble de contraintes

▶ avec des approches de résolution souvent communes

Motivation :

▶ Cadre flexible
➥ on peut résoudre des puzzles, de l’ordonnancement, du partitionnement, de la coloration de graphe, etc.

▶ Résolution automatique et générique

➥ sans écrire un algorithme spécifique pour chaque problème

A. Ouali Programmation Par Contraintes (PPC) 4 / 58

Processus de prise de décision

Formulation Modélisation Algorithme Implémentation

du problème mathématique de résolution de la solution

Solution

Étape suivante

Retour arrière

A. Ouali Programmation Par Contraintes (PPC) 5 / 58

Contraintes

▶ Une variable (inconnues) admet un domaine d’instanciation de valeurs

➠ exemple d’un domaine d’une variable :
x1 = x2 = x3 = {1, 2, 3}

A. Ouali Programmation Par Contraintes (PPC) 6 / 58

Contraintes

▶ Une variable (inconnues) admet un domaine d’instanciation de valeurs

➠ exemple d’un domaine d’une variable :
x1 = x2 = x3 = {1, 2, 3}

▶ Une contrainte est une relation logique sur un nombre fini de variables
Elle n’est pas "dirigée" comme une fonction, et elle est déclarative
➠ exemple d’une contrainte sur deux variables :
(x1 = 1 ↔ x2 = 1), (x1 = 2 ↔ x2 = 2), (x1 = 3 ↔ x2 = 3)

A. Ouali Programmation Par Contraintes (PPC) 6 / 58

Contraintes

▶ Une variable (inconnues) admet un domaine d’instanciation de valeurs

➠ exemple d’un domaine d’une variable :
x1 = x2 = x3 = {1, 2, 3}

▶ Une contrainte est une relation logique sur un nombre fini de variables
Elle n’est pas "dirigée" comme une fonction, et elle est déclarative
➠ exemple d’une contrainte sur deux variables :
(x1 = 1 ↔ x2 = 1), (x1 = 2 ↔ x2 = 2), (x1 = 3 ↔ x2 = 3)

▶ Une contrainte restreint les valeurs que peuvent prendre simultanément les variables qu’elle relie :
➠ instanciations interdites par la contrainte :
hhh hh hh
↔h
(x1 = 1 h x2h=h 2), (x1 =h1h ↔hx2h =h3), (x1 =h ↔h x2h
hh 2 h =h1),
h
h h h h
h ↔h
(x1 = 2 h x2h=h 3), (x1 = 3 h
h ↔hx2h =h 3 ↔h
1), (x1 =h x2h=h2)

A. Ouali Programmation Par Contraintes (PPC) 6 / 58

Contraintes

▶ Une variable (inconnues) admet un domaine d’instanciation de valeurs

➠ exemple d’un domaine d’une variable :
x1 = x2 = x3 = {1, 2, 3}

▶ Une contrainte est une relation logique sur un nombre fini de variables
Elle n’est pas "dirigée" comme une fonction, et elle est déclarative
➠ exemple d’une contrainte sur deux variables :
(x1 = 1 ↔ x2 = 1), (x1 = 2 ↔ x2 = 2), (x1 = 3 ↔ x2 = 3)

▶ Une contrainte restreint les valeurs que peuvent prendre simultanément les variables qu’elle relie :
➠ instanciations interdites par la contrainte :
hhh hh hh
↔h
(x1 = 1 h x2h=h 2), (x1 =h1h ↔hx2h =h3), (x1 =h ↔h x2h
hh 2 h =h1),
h
h h h h
h ↔h
(x1 = 2 h x2h=h 3), (x1 = 3 h
h ↔hx2h =h 3 ↔h
1), (x1 =h x2h=h2)

▶ L’ordre dans lequel sont posées les contraintes n’est pas significatif
Toutes les contraintes sont satisfaites à la fin
Néanmoins, l’efficacité de la résolution est impactée dans certains langages en PPC

A. Ouali Programmation Par Contraintes (PPC) 6 / 58

Modélisation en problème de satisfaction de contraintes

Un CSP (Constraint Satisfaction Problem) est défini par un triplet P = (X, D, C) :

A. Ouali Programmation Par Contraintes (PPC) 7 / 58

Modélisation en problème de satisfaction de contraintes

Un CSP (Constraint Satisfaction Problem) est défini par un triplet P = (X, D, C) :

CSP
▶ X = {x1 , . . . , xn } un ensemble fini de n variables

▶ D une fonction associant à chaque variable xi un domaine fini de valeurs D(xi ), 1 ≤ i ≤ n

▶ C = {C1 , . . . , Cm } un ensemble fini de m contraintes sur les variables du problème P

A. Ouali Programmation Par Contraintes (PPC) 7 / 58

Définition d’une contrainte

Définition en extension : toutes les valeurs autorisées des variables dans la portée de la contrainte sont
explicitement spécifiées :
▶ (x1 = 1 ↔ x2 = 1)
▶ (x1 = 2 ↔ x2 = 2)
▶ (x1 = 3 ↔ x2 = 3)

A. Ouali Programmation Par Contraintes (PPC) 8 / 58

Définition d’une contrainte

Définition en extension : toutes les valeurs autorisées des variables dans la portée de la contrainte sont
explicitement spécifiées :
▶ (x1 = 1 ↔ x2 = 1)
▶ (x1 = 2 ↔ x2 = 2)
▶ (x1 = 3 ↔ x2 = 3)

Définition en compréhension : la relation entre les variables impliquées est exprimée en fonction d’opérateurs
arithmétiques quand c’est possible, ou avec un nom quand la contrainte est complexe :
▶ x1 = x2 , ou
▶ égalité(x1 , x2 )

A. Ouali Programmation Par Contraintes (PPC) 8 / 58

Instanciation et Solution d’un CSP

▶ Une instanciation associe à chacune des variables du CSP un élément de son domaine
➠ c’est un élément du produit cartésien : D(x1 ) × ... × D(xn )

{1,2,3} × {1,2,3} = {(1,1), (1, 2), (1, 3), (2, 1), . . . , (3, 3)}
| {z } | {z }
x1 x2

A. Ouali Programmation Par Contraintes (PPC) 9 / 58

Instanciation et Solution d’un CSP

▶ Une instanciation associe à chacune des variables du CSP un élément de son domaine
➠ c’est un élément du produit cartésien : D(x1 ) × ... × D(xn )

{1,2,3} × {1,2,3} = {(1,1), (1, 2), (1, 3), (2, 1), . . . , (3, 3)}
| {z } | {z }
x1 x2

▶ Une solution est une instanciation satisfaisant chacune des contraintes du CSP

➠ Si dans chaque contrainte on remplace chacune des variables dans sa portée par la valeur que lui affecte
l’instanciation, alors ladite contrainte s’évalue à vrai

A. Ouali Programmation Par Contraintes (PPC) 9 / 58

Cryptarithmétique : SEND + MORE = MONEY

Description du problème
Dans cette addition cryptée sur différentes lettres, on considère que :
▶ une lettre ne peut être associée qu’un chiffre, et
▶ aucune lettre n’a le même chiffre d’une autre lettre.

Question
Quelle est la valeur du mot MONEY et les chiffres associés aux différentes lettres qui vérifient l’équation de
l’addition suivante :

S E N D

+ M O R E

= M O N E Y

A. Ouali Programmation Par Contraintes (PPC) 10 / 58

Modélisation CSP : SEND + MORE = MONEY

S E N D

+ M O R E

= M O N E Y
Variables :

A. Ouali Programmation Par Contraintes (PPC) 11 / 58

Modélisation CSP : SEND + MORE = MONEY

S E N D

+ M O R E

= M O N E Y
Variables :
▶ {S, E, N, D, M, O, R et Y }

A. Ouali Programmation Par Contraintes (PPC) 11 / 58

Modélisation CSP : SEND + MORE = MONEY

S E N D

+ M O R E

= M O N E Y
Variables :
▶ {S, E, N, D, M, O, R et Y }
▶ {r1 , r2 et r3 }

A. Ouali Programmation Par Contraintes (PPC) 11 / 58

Modélisation CSP : SEND + MORE = MONEY

S E N D

+ M O R E

= M O N E Y
Variables :
▶ {S, E, N, D, M, O, R et Y }
▶ {r1 , r2 et r3 }

Domaines :

A. Ouali Programmation Par Contraintes (PPC) 11 / 58

Modélisation CSP : SEND + MORE = MONEY

S E N D

+ M O R E

= M O N E Y
Variables :
▶ {S, E, N, D, M, O, R et Y }
▶ {r1 , r2 et r3 }

Domaines :
▶ D(S) = D(E), . . . , D(Y ) = {0, 1, . . . , 9}

A. Ouali Programmation Par Contraintes (PPC) 11 / 58

Modélisation CSP : SEND + MORE = MONEY

S E N D

+ M O R E

= M O N E Y
Variables :
▶ {S, E, N, D, M, O, R et Y }
▶ {r1 , r2 et r3 }

Domaines :
▶ D(S) = D(E), . . . , D(Y ) = {0, 1, . . . , 9}
▶ D(r1 ) = D(r2 ) = D(r3 ) = {0, 1}

A. Ouali Programmation Par Contraintes (PPC) 11 / 58

CSP : SEND + MORE = MONEY

r3 r2 r1

S E N D

+ M O R E

= M O N E Y
Contraintes :
▶ D + E = Y + 10 × r1
▶ r1 + N + R = E + 10 × r2
▶ r2 + E + O = N + 10 × r3
▶ r3 + S + M = O + 10 × M

A. Ouali Programmation Par Contraintes (PPC) 12 / 58

CSP : SEND + MORE = MONEY

r3 r2 r1

S E N D

+ M O R E

= M O N E Y
Contraintes :
▶ D + E = Y + 10 × r1
▶ r1 + N + R = E + 10 × r2
▶ r2 + E + O = N + 10 × r3
▶ r3 + S + M = O + 10 × M
▶ alldif f erent(S, E, N, D, M, O, R et Y )

A. Ouali Programmation Par Contraintes (PPC) 12 / 58

Solution : SEND + MORE = MONEY

Le solveur nous a retourné la solution :

r3 r2 r1 0 1 1

S E N D 9 5 6 7

+ M O R E + 1 0 8 5

= M O N E Y = 1 0 6 5 2

MONEY = 10652 est la somme qu’il faudrait envoyer.

▶ Chaque valeur trouvée appartient au domaine de la variable

▶ Toutes les contraintes sont satisfaites par cette solution

A. Ouali Programmation Par Contraintes (PPC) 13 / 58

Observations : SEND + MORE = MONEY

r3 r2 r1

S E N D

+ M O R E

= M O N E Y

Modèle CSP amélioré

Écrire un modèle CSP équivalent au CSP précédent mais qui est plus réduit en considérant les différentes
observations sur la modélisation CSP précédente.

A. Ouali Programmation Par Contraintes (PPC) 14 / 58

Exemple : le problème de coloriage d’un graphe

Description
On dispose d’un graphe non orienté représentant une
carte des pays à colorier avec une fonction associant à A S
chaque nœud du graphe un ensemble de couleurs
permises, où :

▶ Les nœuds du graphe sont les différents pays de la F

carte, ainsi la couleur associée à un nœud est celle
du pays correspondant.

▶ Trois couleurs sont disponibles

E I
▶ Deux nœuds sont adjacents si et seulement si les
pays correspondants ont une frontière terrestre
commune

A. Ouali Programmation Par Contraintes (PPC) 15 / 58

Exemple : le problème de coloriage d’un graphe

A S

Question
Trouver le modèle CSP pour colorier les nœuds du graphe, F
chacun avec une couleur de l’ensemble que lui associe la
fonction cl, de telle sorte que deux noeuds adjacents (i.e.,
reliés par une arête) n’aient pas la même couleur ?

E I

A. Ouali Programmation Par Contraintes (PPC) 15 / 58

Exemple : le problème de coloriage d’un graphe

A S

E I

A. Ouali Programmation Par Contraintes (PPC) 16 / 58

Exemple : le problème de coloriage d’un graphe

A S
▶ Variables :
▶ A, S, F, I et E

▶ Domaines :
▶ {rouge, vert, bleu} F

E I

A. Ouali Programmation Par Contraintes (PPC) 16 / 58

Exemple : le problème de coloriage d’un graphe

A S
▶ Variables :
▶ A, S, F, I et E

▶ Domaines :
▶ {rouge, vert, bleu} F

▶ Contraintes :
▶ A ̸= S, A ̸= F, S ̸= F,
▶ S≠ I, F ̸= I et F ̸= E E I

A. Ouali Programmation Par Contraintes (PPC) 16 / 58

Solution : le problème de coloriage d’un graphe

A S

▶ Le solveur nous a retourné la solution suivante :

▶ A = E = I = rouge, F
▶ S = vert, et

▶ F = bleu

E I

A. Ouali Programmation Par Contraintes (PPC) 17 / 58

Types de CSP

Portée d’une contrainte (scope en anglais) est l’ensemble des variables impliquées dans la contrainte.
On définit les variables {case1 , case2 , case3 } et on considère les contraintes suivantes :

▶ case1 = 3, sa portée : {case1 }

▶ case2 + case3 = 12, sa portée : {case2 , case3 }

A. Ouali Programmation Par Contraintes (PPC) 18 / 58

Types de CSP

Portée d’une contrainte (scope en anglais) est l’ensemble des variables impliquées dans la contrainte.
On définit les variables {case1 , case2 , case3 } et on considère les contraintes suivantes :

▶ case1 = 3, sa portée : {case1 }

▶ case2 + case3 = 12, sa portée : {case2 , case3 }

CSP binaire
Chacune des contraintes porte sur au plus deux variables, si on prend l’ensemble de variables
{x1 , x2 , x3 , . . . , xn } :
▶ x1 = 3 (unaire)
▶ x1 = x2 (binaire)
Exemple de contraintes qui ne doivent pas apparaître dans ce type de CSP :
▶ h
x1 h
+hx3 h=hx2 (ternaire)
hh
▶ alldifh
f erent(x
hhh1h . , xn ) (n-aires)
, . .h
h
h

A. Ouali Programmation Par Contraintes (PPC) 18 / 58

Types de CSP

CSP discret

Toutes les variables du CSP ont un domaine fini

▶ Un sous-ensemble fini de nombres pairs :

D10 (P airs) = {0, 2, 4, 6, 8, 10}

▶ Un ensemble fini de couleurs :

D(Couleurs) = {Blue, V ert, Blanc}

▶ Un ensemble de personnes :
D(Étudiant) = {Ania, Inès, Y un}

A. Ouali Programmation Par Contraintes (PPC) 19 / 58

Types de CSP

CSP continu

Le domaine de chacune des variables est continu

▶ Un ensemble continu des points du temps, noté T :

▶ Un ensemble continu des points du plan, noté T 2 :

intervalles de temps où toutes les paires (d,f) de T 2 vérifiant d < f

Exemple : temps de début et de fin des observations du télescope Hubble

A. Ouali Programmation Par Contraintes (PPC) 20 / 58

CSP binaire discret

P = (X, D, C)

▶ X = {x1 , x2 , . . . , xn }

▶ D = {D(x1 ), D(x2 ), . . . , D(xn )} : tous les domaines sont discrets et finis

▶ C = {c1 , c2 . . . , cm } : toutes les contraintes sont unaires ou binaires

Exemple :
▶ X = {x1 , x2 }
▶ D(x1 ) = D(x2 ) = {1, 2, . . . , 100}
▶ C = {1 ≤ x1 ≤ 9, x21 = x2 }

A. Ouali Programmation Par Contraintes (PPC) 21 / 58

Représentation graphique d’un CSP binaire

▶ Un CSP binaire discret P = (X, D, C) est un graphe orienté étiqueté G = (X, E, L) défini comme suit :

A. Ouali Programmation Par Contraintes (PPC) 22 / 58

Représentation graphique d’un CSP binaire

▶ Un CSP binaire discret P = (X, D, C) est un graphe orienté étiqueté G = (X, E, L) défini comme suit :

▶ L’ensemble des sommets de G est l’ensemble des variables X de P

A. Ouali Programmation Par Contraintes (PPC) 22 / 58

Représentation graphique d’un CSP binaire

▶ Un CSP binaire discret P = (X, D, C) est un graphe orienté étiqueté G = (X, E, L) défini comme suit :

▶ L’ensemble des sommets de G est l’ensemble des variables X de P

▶ Pour toute contrainte binaire ck (xi , xj ), G contient un seul arc (xi , xj ) ou (xj , xi ), sinon aucun

A. Ouali Programmation Par Contraintes (PPC) 22 / 58

Représentation graphique d’un CSP binaire

▶ Un CSP binaire discret P = (X, D, C) est un graphe orienté étiqueté G = (X, E, L) défini comme suit :

▶ L’ensemble des sommets de G est l’ensemble des variables X de P

▶ Pour toute contrainte binaire ck (xi , xj ), G contient un seul arc (xi , xj ) ou (xj , xi ), sinon aucun

▶ Pour tout arc (xi , xj ) de G, l’étiquette de (xi , xj ) est l’intersection de toutes les matrices booléennes Mk (xi , xj )
représentant les relations Rk (xi , xj ) associées aux différentes contraintes ck (xi , xj ) de P

A. Ouali Programmation Par Contraintes (PPC) 22 / 58

Représentation graphique d’un CSP binaire

▶ Un CSP binaire discret P = (X, D, C) est un graphe orienté étiqueté G = (X, E, L) défini comme suit :

▶ L’ensemble des sommets de G est l’ensemble des variables X de P

▶ Pour toute contrainte binaire ck (xi , xj ), G contient un seul arc (xi , xj ) ou (xj , xi ), sinon aucun

▶ Pour tout arc (xi , xj ) de G, l’étiquette de (xi , xj ) est l’intersection de toutes les matrices booléennes Mk (xi , xj )
représentant les relations Rk (xi , xj ) associées aux différentes contraintes ck (xi , xj ) de P

Exemple
▶ X = {x1 , x2 }
▶ D(x1 ) = D(x2 ) = {1, 2, 3}
▶ C = {x1 >= x2 , x1 = x2 + 1}

A. Ouali Programmation Par Contraintes (PPC) 22 / 58

Représentation graphique d’un CSP binaire

▶ Un CSP binaire discret P = (X, D, C) est un graphe orienté étiqueté G = (X, E, L) défini comme suit :

▶ L’ensemble des sommets de G est l’ensemble des variables X de P

▶ Pour toute contrainte binaire ck (xi , xj ), G contient un seul arc (xi , xj ) ou (xj , xi ), sinon aucun

▶ Pour tout arc (xi , xj ) de G, l’étiquette de (xi , xj ) est l’intersection de toutes les matrices booléennes Mk (xi , xj )
représentant les relations Rk (xi , xj ) associées aux différentes contraintes ck (xi , xj ) de P

Exemple
▶ X = {x1 , x2 } h 0 0 0
i
x1 1 0 0 x2
▶ D(x1 ) = D(x2 ) = {1, 2, 3} 0 1 0
▶ C = {x1 >= x2 , x1 = x2 + 1}

A. Ouali Programmation Par Contraintes (PPC) 22 / 58

 Résolution d’un CSP

A. Ouali Programmation Par Contraintes (PPC) 23 / 58

Instanciation

▶ L’instanciation d’une variable est le couple (variable, valeur) où valeur est un des éléments du domaine de la
variable

▶ Une instanciation est partielle s’il y a des variables du CSP ayant un domaine contenant deux ou plusieurs
valeurs

▶ Une instanciation est complète si le domaine de chaque variable du CSP a une valeur

A. Ouali Programmation Par Contraintes (PPC) 24 / 58

Instanciation

▶ L’instanciation d’une variable est le couple (variable, valeur) où valeur est un des éléments du domaine de la
variable

▶ Une instanciation est partielle s’il y a des variables du CSP ayant un domaine contenant deux ou plusieurs
valeurs

▶ Une instanciation est complète si le domaine de chaque variable du CSP a une valeur

Exemple : variables = {couleurToit et couleurCapot}

▶ (couleurToit, "noir") incomplète

▶ (couleurCapot, "rouge") incomplète
▶ (couleurToit, "noir"), (couleurCapot, "rouge") complète

A. Ouali Programmation Par Contraintes (PPC) 24 / 58

Vérification d’une contrainte

▶ Une contrainte se vérifie sur une instanciation

▶ Une contrainte est vérifiée (ou satisfaite) si les valeurs des variables respectent la contrainte

A. Ouali Programmation Par Contraintes (PPC) 25 / 58

Vérification d’une contrainte

▶ Une contrainte se vérifie sur une instanciation

▶ Une contrainte est vérifiée (ou satisfaite) si les valeurs des variables respectent la contrainte

Exemple : (variables : A={1,2,3} et B={0,1,2,3}, contrainte : A + B = 2)

▶ {(A, 2)}, pas toute la portée assignée, invérifiable

▶ {(A, 2),(B, 2)}, toute la portée assignée, vérifiable

▶ 2+2=2 est faux, non satisfaite

▶ {(A, 2),(B, 0)}, toute la portée assignée, vérifiable

▶ 2+0=2 est vrai, satisfaite

A. Ouali Programmation Par Contraintes (PPC) 25 / 58

Solution

▶ Une solution est une instanciation complète et valide

Exemples : (contrainte A + B = 2)

▶ {(A,2)}, non complète : pas une solution

▶ {(A,2),(B,2)}, complète, mais invalide : pas une solution

▶ {(A,2),(B,0)}, complète et valide : une solution

A. Ouali Programmation Par Contraintes (PPC) 26 / 58

Architecture d’un solveur de PPC

1. Réduction du problème CSP

▶ Exécuter des algorithmes sur les contraintes du CSP sans faire d’hypothèses

▶ Obtenir un CSP plus simple (instanciation de variables, réduire les domaines) et cohérent

▶ Dans certaines situations, un retour immédiatement (backtracker) est possible : pas de solution au problème

➥ arcs de cohérence : calcul et réduction des domaines

A. Ouali Programmation Par Contraintes (PPC) 27 / 58

Architecture d’un solveur de PPC

2. Explorations de l’espace de solutions avec une hypothèse

▶ Choix d’une variable xi ∈ X non instanciée

▶ Choix d’une valeur k ∈ D(xi ) non explorée

▶ Utilisation des heuristiques

➥ Prendre en compte la spécificité du problème pour trouver rapidement des solutions

➥ Filtrage qui réduit bien les domaines des variables à partir des choix causés initialement

A. Ouali Programmation Par Contraintes (PPC) 28 / 58

Architecture d’un solveur de PPC

3. Vérification de l’hypothèse

▶ Pour toute contrainte ck où xi se trouve dans sa portée :

▶ Contrainte avec toutes les variables instanciées : évaluer la contrainte ck

▶ Contrainte avec des variables non-instanciées : algorithmes de prospection

➥ Réduction des domaines des variables futures

A. Ouali Programmation Par Contraintes (PPC) 29 / 58

Architecture d’un solveur de PPC
4. Validation

1. Succès :

▶ Empiler les choix faits par l’hypothèse

▶ Retourner à l’étape (1.) s’il reste des variables à instancier

▶ Enregistrer la solution dans le cas contraire

▶ Retour en arrière pour continuer l’exploration de l’arbre

2. Échec :

▶ Choisir une nouvelle valeur s’il reste des valeurs non explorées pour la variable de l’hypothèse

▶ Restaurer le contexte en dépilant le dernier choix fait par l’hypothèse

▶ Rechercher une nouvelle valeur pour l’hypothèse précédente

A. Ouali Programmation Par Contraintes (PPC) 30 / 58

Résolution

1. Algorithmes complets de recherche de solutions

2. Techniques d’exploitation de contraintes

3. Techniques rétrospectives et prospectives

A. Ouali Programmation Par Contraintes (PPC) 31 / 58

▶ Recherche systématique d’une solution :

▶ Générer et Tester GT

▶ BackTrack (Simple Retour Arrière)

▶ Techniques prospectives :

▶ Forward checking FC

▶ Looking ahead LA

A. Ouali Programmation Par Contraintes (PPC) 32 / 58

Générer et Tester (GT )

Algorithme complet naïf de recherche de solutions

Initialement, aucune instanciation n’est marquée

1. On génère une instanciation complète non marquée

➥ I = {(x1 , v1 ), (x2 , v2 ), . . . , (xn , vn )}, vn ∈ D(xn )

2. Marquer l’instanciation I

3. Tester si les contraintes sont satisfaites par I

4. Si oui, I est une solution

5. Sinon, recommencer depuis 1

A. Ouali Programmation Par Contraintes (PPC) 33 / 58

Algorithme GT (1/2)

Une fonction récursive booléenne GT pour un CSP P = (X, D, C) dont on doit tester la consistance :

1. P passage par adresse

2. I passage par valeur

3. La fonction GT est appelée initialement avec I vide, aucune variable n’est instanciée

4. GT retourne vrai ssi P est consistant, sinon elle retourne faux

A. Ouali Programmation Par Contraintes (PPC) 34 / 58

Algorithme GT (2/2)

Algorithme 1 : Pseudo-code de GT
Entrées :
▶ Un CSP P = (X, D, C) // membre de la classe
▶ Une instantiation partielle I // argument donné à la fonction GT
Output : Booléen

A. Ouali Programmation Par Contraintes (PPC) 35 / 58

Algorithme GT (2/2)

Algorithme 2 : Pseudo-code de GT
Entrées :
▶ Un CSP P = (X, D, C) // membre de la classe
▶ Une instantiation partielle I // argument donné à la fonction GT
Output : Booléen

Fonction GT(I)
si |Variables(I)|=|X| alors
si Évaluer(I) alors
retourner Vrai
sinon
retourner Faux

sinon
Choisir une variable xi ∈ X qui n’est pas encore instanciée
pour vi ∈ D(xi ) faire
si GT (I ∪ (xi , vi )) alors
retourner Vrai
retourner Faux

A. Ouali Programmation Par Contraintes (PPC) 35 / 58

Algorithme GT (2/2)

Algorithme 3 : Pseudo-code de GT
Entrées :
▶ Un CSP P = (X, D, C) // membre de la classe
▶ Une instantiation partielle I // argument donné à la fonction GT
Output : Booléen

Fonction GT(I)
si |Variables(I)|=|X| alors
si Évaluer(I) alors
retourner Vrai
sinon
retourner Faux

sinon
Choisir une variable xi ∈ X qui n’est pas encore instanciée
pour vi ∈ D(xi ) faire
si GT (I ∪ (xi , vi )) alors
retourner Vrai
retourner Faux

Fonction Évaluer(I)
pour c ∈ C faire
si ¬ c.Satisfait(I) alors
retourner Faux
retourner Vrai

A. Ouali Programmation Par Contraintes (PPC) 35 / 58

Générer et Tester

Inconvénient majeur :

▶ Parcours exhaustif de toutes les instanciations possibles

➥ Borne supérieure : | max1≤i≤n D(xi )|n possibilités

1. Si inexistence de solutions

2. Unique solution consistant en la toute dernière instanciation

A. Ouali Programmation Par Contraintes (PPC) 36 / 58

BackTrack

▶ Retour en arrière est appliqué quand la valeur choisie pour la variable en cours d’instanciation n’est pas
validée avec l’instanciation partielle sur l’ensemble de contraintes possibles

▶ Continuer sur une valeur dans le domaine

▶ Si toutes les valeurs sont explorées :

▶ Retourner échec s’il s’agit de la 1er variable (racine)

▶ Retourner à la variable précédente et continuer l’exploration

▶ Si toutes les contraintes à vérifier sont satisfaites :

▶ Retourner succès s’il s’agit de la toute dernière variable

▶ Passer à la variable suivante et continuer l’exploration

A. Ouali Programmation Par Contraintes (PPC) 37 / 58

Algorithme de BackTrack

Algorithme 4 : Pseudo-code de BackTrack

Entrées :
▶ Un CSP P = (X, D, C) // membre de la classe BacktrackSolver
▶ Une instantiation partielle I // argument donné à la fonction BT
▶ Les variables non instanciées V // argument donné à la fonction BT (classe LinkedList dans le
TP)
Output : Solution

Fonction BT(I, V)
// condition d’arrêt de la récurrsivité
si V = ∅ alors
retourner I
// choisir une variable non encore instanciée
xi ← Retirer(V)
// choisir une valeur dans le domaine de xi
pour vi ∈ D(xi ) faire
N ← I ∪ (xi , vi )
si IsConsistent(N ) alors
R ← BT(N , V)
si R ̸= N ul alors
retourner R
Mettre(V, xi )
retourner Nul

Fonction IsConsistent(N )
pour c ∈ C faire
si Portée(c) ⊆ Variables(N ) alors
si ¬ c.Satisfait(N ) alors
retourner Faux
retourner Vrai

A. Ouali Programmation Par Contraintes (PPC) 38 / 58

BackTrack

TP :
À partir d’une instanciation vide, appeler la fonction BT() dans la méthode solve() de la classe BacktrackSolver.

Avantage :

▶ Espace de recherche est réduit uniquement sur des instanciations

partielles satisfaisant les contraintes avec les variables déjà instanciées

Inconvénient :

▶ Détection des conflits reste tardive

➥ On peut faire mieux avec des techniques prospectives

A. Ouali Programmation Par Contraintes (PPC) 39 / 58

Forward Checking FC

▶ Supprimer des domaines des variables non encore instanciées les valeurs qui ne sont pas compatibles avec
la valeur choisie (anticiper)

▶ ED : un argument de plus pour suivre l’évolution des domaines

➥ passage par valeur

A. Ouali Programmation Par Contraintes (PPC) 40 / 58

Algorithme de FC

Algorithme 5 : Pseudo-code de FC
Entrées :
▶ Un CSP P = (X, D, C) // membre d’une classe
▶ Une instantiation partielle I // arugment de la fonction FC
▶ Les variables non instanciées V // argument donné à la fonction BT (classe LinkedList dans le
TP)
▶ Suivre l’évolution des domaines ED // arugment de la fonction FC
Output : Solution

A. Ouali Programmation Par Contraintes (PPC) 41 / 58

Algorithme de FC

Algorithme 6 : Pseudo-code de FC
Entrées :
▶ Un CSP P = (X, D, C) // membre d’une classe
▶ Une instantiation partielle I // arugment de la fonction FC
▶ Les variables non instanciées V // argument donné à la fonction BT (classe LinkedList dans le
TP)
▶ Suivre l’évolution des domaines ED // arugment de la fonction FC
Output : Solution
Fonction FC(I, V, ED)
// condition d’arrêt de la récurrsivité
si V = ∅ alors
retourner I
sinon
// choisir une variable non encore instanciée
xi ← Retirer(V)
pour vi ∈ ED(xi ) satisfaisant les contraintes unaire sur xi faire
V′ ← V
D′ = ED ; D′ (xi ) = {vi } ; domaineVide=Faux

tant que V ′ ̸= ∅ ∧ ¬domaineVide faire

// Considérer une variable xj de l’ensemble V ′
xj ← Retirer(V ′ )
D(xj ) = {vj ∈ ED(xj )|{(xi , vi ), (xj , vj )} satisfait les contraintes}
si D′ (xj ) = ∅ alors domaineVide=Vrai

R ← FC(I ∪ {(xi , vi )}, V ′ , D′ )

si ¬domaineVide ∧ R ̸= N ul alors
retourner R

Mettre(V, xi )
retourner Nul

A. Ouali Programmation Par Contraintes (PPC) 41 / 58

Forward Checking

Inconvénient :

▶ Ne supprime que les valeurs incompatibles avec la valeur choisie pour la variable en cours d’instanciation

▶ Il peut y avoir des xi et xj non encore instanciées où ED(xi ) peut avoir des valeurs n’ayant plus de support
dans ED(xj )

A. Ouali Programmation Par Contraintes (PPC) 42 / 58

Look-Ahead

▶ Filtrage avec un algorithme de cohérence locale

▶ Cohérence de nœud

▶ Cohérence d’arc (AC1 et AC3)

▶ Filtrage durant la recherche récursive d’une solution

▶ Avant le début effectif de la recherche (prétraitement)

▶ Après chaque instanciation

▶ Heuristiques

▶ Choix de variables

▶ Choix de valeurs

A. Ouali Programmation Par Contraintes (PPC) 43 / 58

Cohérence locale

▶ Incomplets en général mais de complexité polynomiale

▶ Cohérence de nœud : cohérence sur des contraintes unaires

▶ Cohérence d’arc : cohérence sur des contraintes unaires et binaires

▶ Cohérence de chemin : cohérence sur des contraintes unaires et binaires

A. Ouali Programmation Par Contraintes (PPC) 44 / 58

Cohérence de nœud NC

Cohérence de nœud (Node Consistency)

▶ Un CSP P = (X, D, C) est cohérent de noeud si pour toute variable xi ∈ X, et pour toute valeur vi ∈ D(xi ) :

➠ l’instanciation partielle {(xi , vi )} satisfait toutes les contraintes unaires dans C portant sur xi
▶ Aucun domaine n’est vide

Principe

▶ Supprimer de D(xi ) toute valeur vi telle que l’instanciation partielle (xi , vi ) viole les contraintes unaires
portant exclusivement sur xi

A. Ouali Programmation Par Contraintes (PPC) 45 / 58

Algorithme de NC

Algorithme 7 : Pseudo-code de NC
Entrées :
▶ Un CSP (X, D, C) // membre de la classe
▶ Un argument pour suivre l’évolution des domaines ED
Output :
▶ Les domaines dans ED vérifient la cohérence de noeud
▶ La fonction retourne Vrai si aucun domaine n’est vide, sinon elle retourne Faux

Fonction enforceNodeConsistency(ED)
pour toute variable x ∈ X faire
pour toute valeur v ∈ ED(x) faire
pour toute contrainte unaire c ∈ C faire
si ¬ c.Satisfait((x, v)) alors
ED(x) ← ED(x) \ {v} // Supprimer v du domaine de x
pour toute variable x ∈ X faire
si ED(x) = ∅ alors retourner Faux
retourner Vrai

A. Ouali Programmation Par Contraintes (PPC) 46 / 58

Support d’une valeur

▶ Soit une contrainte binaire c portant sur xi , xj ∈ X

▶ La valeur (xj , vj ) est support de la valeur (xi , vi ) pour la contrainte c si et seulement si (vi , vj ) satisfait c

▶ Une valeur est viable si et seulement si elle possède au moins un support pour chacune des contraintes
portant sur elle

A. Ouali Programmation Par Contraintes (PPC) 47 / 58

Support d’une valeur

▶ Soit une contrainte binaire c portant sur xi , xj ∈ X

▶ La valeur (xj , vj ) est support de la valeur (xi , vi ) pour la contrainte c si et seulement si (vi , vj ) satisfait c

▶ Une valeur est viable si et seulement si elle possède au moins un support pour chacune des contraintes
portant sur elle

Par exemple :
▶ X : {x1 , x2 , x3 }, D(x1 ) = D(x2 ) = D(x3 ) = {1, 2, 3}
▶ C = {x1 < x2 et x2 = x3 }

▶ (x2 , 2) et (x2 , 3) sont support de (x1 , 1) pour x1 < x2 donc (x1 , 1) est viable
▶ (x2 , 3) est support de (x1 , 2) pour x1 < x2 donc (x1 , 2) est viable
▶ il n’y a pas de support de (x1 , 3) pour x1 < x2 donc (x1 , 3) est non viable

A. Ouali Programmation Par Contraintes (PPC) 47 / 58

Arc Cohérence (AC)

Arc cohérence (Arc Consistency)

▶ Un CSP P = (X, D, C) est arc cohérent si :

▶ Il vérifie la cohérence de nœud
▶ Pour tout couple de variables (xi , xj ), et pour toute valeur vi ∈ D(xi ), l’instanciation {(xi , vi )} est viable pour xj sur
toutes les contraintes binaires de C portant exclusivement sur xi et xj

Principe

▶ Rendre le CSP cohérent de nœud

▶ Supprimer de D(xi ) toute valeur vi non viable sur des contraintes binaires portant sur la variable xi et une
variable xj

A. Ouali Programmation Par Contraintes (PPC) 48 / 58

Algorithmes de AC

▶ Revise
▶ Réduit la taille des domaines

▶ Supprime les valeurs non viables

▶ AC1 :
▶ Applique autant que possible Revise à tous les arcs sur lesquels il y a une contrainte

▶ Si aucun domaine n’a été modifié, la procédure prend fin

▶ Réapplique Revise à tous les arcs, même aux arcs non modifiés par la passe précédente

▶ AC3 :
▶ Ne réapplique Revise qu’aux arcs dont le domaine de la variable extrémité a été modifié
➥ (xk , xi ) tel que D(xi ) modifié

A. Ouali Programmation Par Contraintes (PPC) 49 / 58

Algorithme de Revise

Algorithme 8 : Pseudo-code de Revise

Entrées :
▶ Un CSP (X, D, C) // membre de la classe
▶ Un argument pour la 1er variable xi
▶ Un argument pour la 2ème variable xj
▶ Un argument pour suivre l’évolution des domaines ED
Output :
▶ Les domaines dans ED vérifient l’arc-cohérence
▶ La fonction retourne V rai si au moins un domaine des variables est réduit, sinon elle retourne F aux

Fonction REVISE(xi , xj , ED)

Del ← F aux
pour toute vi ∈ ED(xi ) faire
viable ← F aux
pour toute vj ∈ ED(xj ) faire
toutSatisf ait ← V rai
pour toute contrainte binaire c ∈ C portant sur xi et xj faire
N ← {(xi , vi ), (xj , vj )}
si ¬ c.Satisfait(N ) alors
toutSatisf ait ← F aux
break
si toutSatisfait alors
viable ← V rai
break
si ¬ viable alors
ED(xi ) ← ED(xi )\{vi } // Supprimer vi du domaine de xi
Del ← V rai
retourner Del

A. Ouali Programmation Par Contraintes (PPC) 50 / 58

Algorithme de AC1

Algorithme 9 : Pseudo-code de AC1

Entrées :
▶ Un CSP (X, D, C) // membre de la classe
▶ Un argument pour suivre l’évolution des domaines ED
Output :
▶ Les domaines ED sont arc-cohérent si aucun domaine n’est vide
▶ La fonction retourne F aux si au moins un domaine est vide, sinon elle retourne V rai

Fonction AC1(ED)
si ¬NC(ED) alors
retourner Faux

faire
change ← F aux
pour tout couple (xi , xj ) dans X faire
si REVISE(xi , xj , ED) alors
change ← V rai

tant que change = V rai

pour toute variable x ∈ X faire

si ED(x) = ∅ alors retourner Faux
retourner Vrai

A. Ouali Programmation Par Contraintes (PPC) 51 / 58

Algorithme de MAC (Maintaining Arc Consistency) solver

Algorithme 10 : Pseudo-code de MAC

Entrées :
▶ Un CSP P = (X, D, C) // membre de la classe BacktrackSolver
▶ Une instantiation partielle I // argument donné à la fonction MAC
▶ Les variables non instanciées V // argument donné à la fonction MAC (classe LinkedList dans le TP)
▶ Suivre l’évolution des domaines ED // arugment de la fonction MAC
Output : Solution

Fonction MAC(I, V, ED)

// conditions d’arrêt de la récurrsivité
si V = ∅ alors
retourner I
sinon
// Réduction des domaines des variables par l’arc-cohérence
si ¬ AC1(X, ED, C) alors
retourner Nul
// choisir une variable non encore instanciée
xi ← Retirer(V)
// choisir une valeur dans le domaine de xi
pour vi ∈ ED(xi ) faire
N ← I ∪ (xi , vi )
si IsConsistent(N ) alors
R ← MAC(N , V, ED)
si R ̸= N ul alors
retourner R
Mettre(V, xi )
retourner Nul

A. Ouali Programmation Par Contraintes (PPC) 52 / 58

 Heuristiques

A. Ouali Programmation Par Contraintes (PPC) 53 / 58

Heuristique

Définition
Méthode permettant en pratique d’obtenir plus rapidement une solution, très souvent non optimale.

▶ Choix de la prochaine variable

▶ Choix de la prochaine valeur

A. Ouali Programmation Par Contraintes (PPC) 54 / 58

Choix de variable

Information sur la variable :

▶ Taille de son domaine

▶ Le nombre de contraintes qui l’utilise

▶ Première/Dernière

▶ Celle avec le domaine le plus petit/grand

▶ Celle dans le plus petit/grand nombre de contraintes

▶ |domaine| / |contraintes|

A. Ouali Programmation Par Contraintes (PPC) 55 / 58

Choix de valeur

Information sur la valeur :

▶ Première/Dernière

▶ Au milieu

▶ Alternance début/fin

A. Ouali Programmation Par Contraintes (PPC) 56 / 58

Choix de valeur

Pourquoi c’est important ?

▶ Ne change pas la taille de l’arbre de recherche

▶ Pas d’effet sur l’énumération des solutions

▶ Mais si on cherche une solution, impact sur le temps nécessaire pour l’obtenir

A. Ouali Programmation Par Contraintes (PPC) 57 / 58

Hasard

Choix aléatoire :

▶ Souvent le hasard fait bien les choses

▶ Peut avoir des gains spectaculaires

▶ Choisir au hasard l’ordre des variables

▶ Choisir au hasard en cas d’ex aequos pour les heuristiques

▶ Choisir une heuristique au hasard

A. Ouali Programmation Par Contraintes (PPC) 58 / 58