Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Programmation par contraintes

Cours 2 : Problmes de Satisfaction de Contraintes e CSP Odile PAPINI
ESIL Universit de la mditerrane e e e [email protected] http://pages-perso.esil.univmed.fr/papini/

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Plan du cours 2

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Bibliographie
Livres : K. Marriott and P. Stuckey. Programming with constraints. MIT Press 1998 F. Fages. Programming Logique par contraintes. Ellipes, 1996 K. R. Apt. Principles in Constraint Programming. Cambridge Univ Press, 2003 Supports de cours : Support de cours : Christine SOLNON universit Lyon e I : http ://bat710.univ-lyon1.fr/ csolnon/Site-PPC/ Roman Bartak Charles university : http ://kti.m.cuni.cz/ bartak/constraints/
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Probl`mes de Satisfaction de Contraintes (CSP) e

Dnition e un CSP est un probl`me modlis sous forme de contraintes poses e e e e sur des variables prenant valeur dans un domaine u un CSP est quadruplet (X , D, C , R) o` : X = {X1 , , Xn } : un ensemble de variables D = {D1 , , Dn } : un ensemble de domaines,
Xi Di , 1 i n

C = {C1 , , Cm } : un ensemble de contraintes, R = {R1 , , Rm } : un ensemble de relations,

` chaque contrainte Cj est associe une relation Rj , 1 j m a e
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Probl`mes de Satisfaction de Contraintes (CSP) e

Exemple X = {X1 , X2 , X3 , X4 } D = {D1 , D2 , D3 , D4 } avec D1 = D2 = D3 = D4 = {0, 1} C = {X1 = X2 , X3 = X4 , X1 + X3 < X2 } R = {R1 , R2 , R3 } Les relations asocies aux contraintes de C : e R1 X1 0 1 X2 1 0 X1 0
Odile PAPINI

R2 X3 0 1 R3 X2 1 X3 0
Programmation par contraintes

X4 1 0

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Modlisation de probl`mes en termes de CSP e e

Modlisation dun probl`me e e identier les variables : les inconnues identier les domaines de valeur de ces variables identier les contraintes souvent plusieurs modlisations possibles, crit`res de choix : e e simplicit dexpression e ecacit : taille de lespace de recherche de solutions e

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Modlisation de probl`mes en termes de CSP e e

Exemple : le probl`me des 4 reines e Placer 4 reines sur chiquier 4 4 de telle sorte quaucune ne soit e en prise (pas sur la mme ligne, pas sur la mme colonne, pas sur e e la mme diagonale) e X = ? D = ? C = ?

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Modlisation de probl`mes en termes de CSP e e

Exemple : le probl`me des 4 reines e Placer 4 reines sur chiquier 4 4 de telle sorte quaucune ne soit e en prise (pas sur la mme ligne, pas sur la mme colonne, pas sur e e la mme diagonale) e X = {X1 , X2 , X3 , X4 } D = {D1 , D2 , D3 , D4 } avec D1 = D2 = D3 = D4 = {1, 2, 3, 4} C = {CLI , CDA , CDD } avec
CLI = {Xi = Xj , i = j, i {1, 2, 3, 4}, j {1, 2, 3, 4}} CDA = {Xi + i = Xj + j, i = j, i {1, 2, 3, 4}, j {1, 2, 3, 4}} CDD = {Xi i = Xj j, i = j, i {1, 2, 3, 4}, j {1, 2, 3, 4}}

Modlisation ecace e
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Rsolution dun CSP e

Rsolution : aectation de valeurs aux variables de telle sorte que e toutes les contraintes soient satisfaites aectation : instanciation des variables sur les domaines aectation totale : aectation de toutes les variables aectation partielle : aectation de certaines variables aectation consistante : aectation qui ne viole aucune contrainte aectation inconsistante : aectation qui viole au moins une contrainte solution : aectation totale et consistante
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Rsolution dun CSP e

Exemple X = {X1 , X2 , X3 , X4 } D = {D1 , D2 , D3 , D4 } avec D1 = D2 = D3 = D4 = {0, 1} C = {X1 = X2 , X3 = X4 , X1 + X3 < X2 } A = {(X2 , 0), (X3 , 1)} aectation A = {(X1 , 0), (X2 , 0), (X3 , 0), (X4 , 0)} aectation totale A = {(X1 , 0), (X2 , 0)} aectation partielle A = {(X1 , 0), (X2 , 0)} aectation inconsistante A = {(X3 , 0), (X4 , 1)} aectation consistante A = {(X1 , 0), (X2 , 1), (X3 , 0), (X4 , 1)} solution
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Rsolution dun CSP e

Rsolution : aectation de valeurs aux variables de telle sorte que e toutes les contraintes soient satisfaites complexit : en gnral probl`me NP-dicile e e e e solution : aectation totale et consistante On peut chercher : une solution, nimporte laquelle toutes les solutions une solution optimale ou au moins une bonne solution selon une fonction de cot ou dobjectif (Probl`me dOptimisation u e de Contraintes (COP))

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Intrt des CSP ee

Intrt des CSP par rapport ` la programmation mathmatique ee a e la reprsentation des CSP est plus proche des probl`mes e e originaux, la formulation est plus simple les algorithmes de rsolution des CSP sont relativement e simples et sont plus rapides que ceux de la programmation en nombres entiers

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Binarisation des contraintes

Les contraintes peuvent tre n-aires : 2 cas particuliers e les contraintes unaires
peuvent tre traites par un pr-traitement sur les domaines e e e

les contraintes binaires

si toutes les contraintes sont binaires : reprsentation par un e graphe dont les sommets sont les variables et les arcs sont les contraintes.

toute contrainte n-aire peut sexprimer en termes de contraintes binaires

Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Binarisation des contraintes

toute contrainte n-aire peut sexprimer en termes de contraintes binaires tout CSP peut se reprsenter comme un CSP binaire e un CSP binaire peut tre reprsent comme un graphe de e e e contraintes exemples

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Binarisation dun CSP

Mthode 1 : conservation de variables initiales e cration dune variable encapsule U e e e e domaine de U : produit cartsien des variables encapsules application des contraintes sur les variables encapsules pour e rduire le domaine e ajout dune binaire entre la variable originale et la variable encapsule : Xi = posi (U) e i`me position de Xi dans U : posi (U) e

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Binarisation dun CSP

Mthode 1 : exemple e X = {X1 , X2 , X3 } D = {D1 , D2 , D3 } avec D1 = {1, 2}, D2 = {3, 4}, D3 = {5, 6} C = {X1 + X2 = X3 , X1 < X2 }
CSP binaire : X = {X1 , X2 , X3 U}, D = {D1 , D2 , D3 , DU } cration de la variable U = {(X1 , X2 , X3 ), tq {X1 + X2 = X3 }, e DU = D1 D2 D3 rduction de domaine : DU e nouvel ensemble de containtes : C

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Binarisation dun CSP

Mthode 2 : sans conservation de variables initiales e cration de variables encapsules e e domaine : produit cartsien des variables quelles encapsulent e application des contraintes sur les variables encapsules pour e rduire le domaine e ajout dune binaire entre la variable originale et la variable encapsule : Xi = posi (U) e i`me position de la variable encapsule U est la j`me position e e e de la variable encapsule V : posi (U) = posj (V ) e
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Binarisation dun CSP

Mthode 2 : exemple e X = {X1 , X2 , X3 } D = {D1 , D2 , D3 } avec D1 = {1, 2}, D2 = {3, 4}, D3 = {5, 6} C = {X1 + X2 = X3 , X1 < X2 }
CSP binaire : X = {U, V }, D = {DU , DV }, C cration de 2 variable U = {(X1 , X2 , X3 ), tq {X1 + X2 = X3 }, et e V = {(X1 , X2 ), tq {X1 < X2 } DU = D1 D2 D3 et DV = D1 D2 rduction de domaine : DU et DV e nouvel ensemble de containtes : C
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Rsolution dun CSP e

hypoth`se : domaines nis e algorithmes gnriques de rsolution de CSP e e e algorithmes complets algorithmes incomplets Autres algorithmes pour : CSP numriques linaires sur les rels e e e CSP numriques linaires sur les entiers e e CSP numriques non linaires e e

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Algorithmes de rsolution dun CSP e

algorithmes gnriques de rsolution de CSP e e e recherche systmatique e
genere et teste (GET) retour arri`re (SRA) ou (backtracking (BT)) e

techniques de ltrage
consistance de noeud (NC), darc (AC), de chemin (PC)

techniques de propagation de contraintes

forward checking (FC) look ahead (LH)

techniques bases sur lordre des variables et des valeurs e

heuristiques
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Approche Gn`re Et Teste e e

principe

Recherche systmatique dune solution e

gnration dun aectation totale e e test de la satisfaction de toutes les contraintes

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Algorithme Gn`re et Teste : GET e e

fonction GET(A,(X,D,C)) : boolen e dbut e si toutes les variables de X sont aectes alors e si A est consistante alors retourner VRAI sinon retourner FAUX nsi sinon choisir une variable Xi de X qui nest pas encore aecte e pour toute valeur Vi appartenant ` Di faire a si GET(A {(Xi ,Vi )}, (X,D,C)) = VRAI alors retourner VRAI nsi n pour retourner FAUX nsi n
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Algorithme Gn`re Et Teste : GET e e

exemple X = {X1 , X2 , X3 , X4 } D = {D1 , D2 , D3 , D4 } avec D1 = D2 = D3 = D4 = {0, 1} C = {X1 = X2 , X3 = X4 , X1 + X3 < X2 } R = {R1 , R2 , R3 } Recherche de solutions de ce CSP par lalgorithme GET

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Algorithme Gn`re Et Teste : GET e e

inconvenients sur lespace de recherche ensemble des aectations compl`tes e inconsistance dcouverte au dernier moment e croissance exponentielle de la taille de lespace de recherche amliorations e ne dvelopper que des aectations partielles consistantes e rduire la taille des domaines e
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Approche Simple retour arri`re e

principe

Construction dune solution

gnration dun aectation partielle consistante e e extension de laectation partielle avec laection dune nouvelle variable si cette extension est inconsistante on retourne en arri`re on e modie laectation de la nouvelle variable

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Algorithme Simple Retour Arri`re : SRA e

fonction SRA(A,(X,D,C)) : boolen e dbut e si A nest pas consistante alors retourner alors retourner FAUX nsi si toutes les variables de X sont aectes alors e retourner VRAI sinon choisir une variable Xi de X qui nest pas encore aecte e pour toute valeur Vi appartenant ` Di faire a si SRA(A {(Xi ,Vi )}, (X,D,C)) = VRAI alors retourner VRAI nsi n pour retourner FAUX nsi n
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Algorithme Simple Retour Arri`re : SRA e

exemple du probl`me des 4 reines e

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Algorithme Algorithme Simple Retour Arri`re : SRA e

avantages rduction de lespace de recherche e amliore GET en espace et en temps dexcution e e inconvenients pas didentication des cause de conit redondance dtection tardive des conits e alternatives : backjumping, backmarking
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Techniques de ltrage

principe

ltrage des domaines

dans la construction dune aectation partielle consistante : ltrage ` priori a ltrer le domaine des variables en enlevant les valeurs localement inconsistantes ltrage ` dirents niveaux : noeud, arc, chemin, a e

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Techniques de ltrage
consistance de noeud Un CSP (X , D, C , R) est consistant de noeud si pour toute variable Xi de X , et pour toute valeur v de Di , laectation partielle {(Xi , v )} satisfait toutes les contraintes unaires de C . principe ltrage des domaines pour chaque variable Xi , on enl`ve de Di toute valeur v telle e que laectation partielle {(Xi , v )} viole les contraintes unaires.
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Techniques de ltrage
consistance darc Un CSP (X , D, C , R) est consistant darc si tout couple de variables (Xi , Xj ) de X , et pour toute valeur vi de Di , il existe une valeur vj appartenant Dj telle que laectation partielle {(Xi , vi ), (Xj , vj )} satisfasse toutes les contraintes binaires de C . principe ltrage des domaines pour chaque variable Xi , on enl`ve de Di toute valeur vi telle e quil existe une variable Xj pour laquelle, pour toute valeur vj de Dj , laectation partielle {(Xi , vi ), (Xj , vj )} viole les contraintes binaires.
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Techniques de ltrage : consistance darc

plusieurs algorithmes AC ou REVISE : rduit la taille des domaines, supprime les e valeurs qui violent les contraintes binaires AC1 : rapplique REVISE chaque fois quun domaine est e chang e AC3 : ne rapplique REVISE que le nombre de fois ncessaires e e

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Algorithme Consistance DArc : AC

fonction REVISE((Xi , Xj ),(X,D,C)) : boolen e dbut e DELETE FAUX pour tous les Vi de Di faire si il ny a pas de Vj dans Dj qui satisfasse les contraintes binaires entre Xi et Xj alors supprimer Vi de Di DELETE VRAI nsi n pour retourner DELETE n

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Algorithme Consistance DArc : AC1

fonction AC1((X,D,C)) dbut e Q {(Xi , Xj ) /il existe une contrainte entre Xi et Xj } rpter R FALSE pour tous les (Xi , Xj ) de Q faire R (R ou REVISE((Xi , Xj ),(X,D,C))) n pour jusqu non R retourner (X,D,C) n

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Algorithme Consistance DArc : AC3

fonction AC3((X,D,C)) dbut e Q {(Xi , Xj ) /il existe une contrainte entre Xi et Xj } tantque Q = faire Q Q \(Xi , Xj ) si REVISE((Xi , Xj ),(X,D,C)) alors Q Q {(Xk , Xi ) /il existe une contrainte entre Xk et Xi et Xk = Xi et Xk = Xj } nsi n tantque retourner (X,D,C) n

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Techniques de ltrage : consistance locale

plusieurs notions 1- consistance : consistance de noeud 2- consistance : consistance darc 3-consistance : consistance de chemin un ensemble {Xi , Xj } est consistant de chemin par rapport ` a la variable Xk de X , si pour toute aectation partielle {(Xi , vi ), (Xj , vj )}, il existe une valeur vk appartenant Dk telle que {(Xi , vi ), (Xk , vk )} est consistant et {(Xk , vk ), (Xj , vj )} est consistant. k-consistance : considrer les valeurs dune variable par e rapport ` la combinaison de k 1 valeurs des autres variables. a
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Techniques de propagation de contraintes

principe

Forward checking et Look-ahead

Combinaison du ltrage et du retour-arri`re : ltrage au cours e de la rsolution e Forward checking : Apr`s chaque aectation dune varible Xi , e ltrer le domaine de la variable Xj non encore aect`es dont e les valeurs violent les contraintes contenant Xi et Xj . Look ahead : Apr`s chaque aectation dune varible Xi , ltrer e le domaine de toutes les variable non encore aect`es dont les e valeurs violent les contraintes contenant Xi et ces variables.
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Techniques de propagation de contraintes

consistance de noeud

Un CSP (X , D, C , R) est consistant de noeud si pour toute variable Xi de X , et pour toute valeur v de Di , laectation partielle {(Xi , v )} satisfait toutes les contraintes unaires de C . principe : anticipation + consistance de noeud anticipation dune tape laectation e pour chaque variable Xi non aecte dans A, on enl`ve de Di e e toute valeur v telle que A {(Xi , v )} est inconsistante.
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Algorithme anticipation : forward checking

fonction FC(A,(X,D,C)) : boolen e dbut e si toutes les variables de X sont aectes alors e retourner VRAI sinon choisir une variable Xi de X qui nest pas encore aecte e pour toute valeur Vi appartenant ` Di faire a pour toute variable Xj de X qui nest pas encore aecte faire e Dj {Vj lment de Dj | A {(Xi , Vi ), (Xj , Vj )} est consistante } ee si Dj est vide alors retourner FAUX nsi n pour si FC(A {(Xi , Vi )},(X,D,C))= VRAI alors retourner VRAI nsi n pour retourner FAUX nsi n Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Algorithme Anticipation : FC

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Techniques de propagation de contraintes

consistance darc Un CSP (X , D, C , R) est consistant darc si tout couple de variables (Xi , Xj ) de X , et pour toute valeur vi de Di , il existe une valeur vj appartenant Dj telle que laectation partielle {(Xi , vi ), (Xj , vj )} satisfasse toutes les contraintes binaires de C . principe : anticipation + consistance darc anticipation de deux tapes laectation e pour chaque variable Xi non aecte dans A, on enl`ve de Di e e toute valeur vi telle quil existe une variable Xj non aecte e pour laquelle, pour toute valeur vj de Dj , laectation A {(Xi , vi ), (Xj , vj )} est inconsistante.
Odile PAPINI Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Algorithme Look ahead : LH

Odile PAPINI

Programmation par contraintes

Dnition dun CSP e Modlisation en termes de CSP e Rsolution dun CSP e Algorithmes de rsolution e

Heuristiques

ordre des variables

statique dynamique

ordre des valeurs

Odile PAPINI

Programmation par contraintes