![Page 1: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/1.jpg)
Méthodes hybrides dans les réseaux de contraintes pondérées
Simon de Givry, Thomas Schiex, INRA ToulouseGérard Verfaillie, Sylvain Bouveret, ONERA Toulouse
Remerciements à Javier Larrosa, UPC Barceloneet Martí Sànchez, CSIC Barcelone
![Page 2: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/2.jpg)
INRA Toulouse
Unité de Biométrie et Intelligence Artificielle (33 pers.) Equipe Statistique et informatique appliquées à la
génétique et à la biologie moléculaire (16 pers.) Réseaux de contraintes pondérées
Recherche de motifs d’ARN fonctionnelsdans les séquences génomiques(~millions nucléotides)
Détection et correction d’erreurs de génotypagedans les pedigrees d’animaux(120000 individus)
Projet ANR sur les méthodes hybrides (2006-2008)
![Page 3: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/3.jpg)
Réseau de contraintes pondérées
Mélange de contraintes dures (modèle physique) et de
contraintes pondérées (préférences)
Fonction retournant un coût qui dépend de la valeur de ses
variables
ex.: W : D(Xi) D(Xj) [ 0, k ] (variables à domaines finis)
But: trouver une affectation complète qui minimise la
sommesomme des coûts des contraintes (< k=T)
En général, problème NP-difficileNP-difficile
Cadre général incluant SAT (T=1), CSP (T=1),
Max-CSP, Max-SAT, MPE, Min-COL, Max-Clique,…
![Page 4: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/4.jpg)
Méthodes complètes usuelles
Recherche arborescente
Depth-First Branch and Bound
Inférence complète
Elimination de variables
![Page 5: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/5.jpg)
Depth-First Branch and Bound
(LB) Minorant
(UB) Majorant
Si UB alors coupe
vari
ab
les
Approximation inférieure de l’optimum du sous-arbre
= meilleure solution trouvée
Chaque nœud est un sous-réseaude contraintes pondérées
LBLB
= T Temps: (exp(n)) Espace: (n) n : nombre de variables
![Page 6: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/6.jpg)
Elimination de variables
Résout le problème par une séquence de
transformations du problème (sans retour-arrière)
Chaque étape conduit à un problème avec une variable
de moins et le même optimum
Lorsque toutes les variables ont été éliminées, le
problème est résolu (inférence complète)
Une/toutes les solutions optimales du problème original
peuvent être obtenues
![Page 7: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/7.jpg)
OPT
Elimination de variables
Choisis une variable xi
Calcule l’ensemble Ki des contraintes qui portent sur la variable
Ajoute Supprime la variable et Ki
Temps: (exp(degi+1)) Espace: (exp(degi))
X4
X3
X5
X2
X1
iiKf
xKfi
][)(
![Page 8: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/8.jpg)
Influence de l’ordre d’élimination
Ordre G,D,F,B,C,A N’ajoute pas de
contraintes induites
Ordre G,B,C,D,F,A Ajoute ACFD (4-clique)
![Page 9: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/9.jpg)
Largeur induite
Soit un graphe et un ordre d’élimination donné, le plus
grand degré rencontré est la largeur induite du graphe
ordonné : w = max(degi) + 1 Complexité de l’algorithme d’élimination de variables
Temps: (n.exp(w)) Espace: (n.exp(w))
Minimiser la largeur induite est NP-dur
Heuristiques
Max Cardinality Search (optimal si graphe chordal)
Min Fill, Min Degree,…
![Page 10: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/10.jpg)
A quoi cela ressemble ?
Un graphe ayant une largeur induite k équivaut àun k-arbre partiel
Un k-arbre est soit une k-clique soit un k-arbre ayant un sommet supplémentaire connecté à tous les sommets d’une k-clique à l’intérieur du k-arbre
1-arbre 2-arbre
![Page 11: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/11.jpg)
Comparaison entre recherche et inférence
Recherche
(DFBB)Élimination de
variables
Complexité temporelle
asymptotiqueO(exp(n))
O(n.exp(w))
w n
Complexité temporelle moyenne
Meilleure qu’au pire cas
Identique au pire cas
Complexité spatiale asymptotique
O(n) O(n.exp(w))
Hybridation de méthodes !
![Page 12: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/12.jpg)
Hybridation de recherche et élimination de variables
DFBB-VE
![Page 13: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/13.jpg)
Recherche avec élimination de variable (Larrosa 2003)
A chaque noeud Choisir une variable non affectée Xi
Si degréi ≤ k Alors élimine Xi
Sinon énumération des valeurs de Xi
Propriétés DFBB-VE(-1) équivaut à DFBB DFBB-VE(w) équivaut à VE DFBB-VE(1) équivaut à l’algorithme Coupe-Cycle
Temps: (exp(l)) avec w* ≤ l ≤ n Espace: (n.exp(k))
![Page 14: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/14.jpg)
Exemple DFBB-VE(2)
![Page 15: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/15.jpg)
Exemple DFBB-VE(2)
![Page 16: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/16.jpg)
Hybridation de recherche et décomposition arborescente(élimination d’arbre de clusters)
CTE
BTD
BTD+
Lc-BTD+
Lc-BTD*
![Page 17: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/17.jpg)
x1 x2 x3
x5x4 x6
x8
x7
x9
Décomposition arborescente
![Page 18: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/18.jpg)
x9
x1 x2 x3
x5x4 x6
x8
x7
Décomposition arborescente
![Page 19: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/19.jpg)
x9
x1 x2 x3
x5x4 x6
x8
x7
Décomposition arborescente
![Page 20: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/20.jpg)
x9
x1 x2 x3
x5x4 x6
x8
x7
Décomposition arborescente
Largeur d’arbre (w) : nombre maximum de variables dans un cluster
= largeur induite du graphe triangulé
![Page 21: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/21.jpg)
x7
x1 x2
x5x4 x6
x3
x5 x6
x8
x2 x3
x5 x6
x9x8
Décomposition arborescente u
r
vp
w
1. chaque variable apparaît dans un seul chemin
![Page 22: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/22.jpg)
x7
x1 x2
x5x4 x6
x3
x5 x6
x8
x2 x3
x5 x6
x9x8
Décomposition arborescenteu
r
vp
w
2. Chaque contrainte est dans exactement un cluster
![Page 23: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/23.jpg)
x7
x1 x2
x5x4 x6
x3
x5 x6
x8
x2 x3
x5 x6
x9x8
u
r
vp
w
Cluster Tree Elimination
( , )m u r
),()(
rusepfuf
![Page 24: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/24.jpg)
x7
x1 x2
x5x4 x6
x3
x5 x6
x8
x2 x3
x5 x6
x9x8
u
r
vp
w
Cluster Tree Elimination
( , )m u r
),()(
rusepfuf
![Page 25: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/25.jpg)
x7
x1 x2
x5x4 x6
x3
x5 x6
x8
x2 x3
x5 x6
x9x8
u
r
vp
w
Cluster Tree Elimination
Un message peut être envoyéen sortie d’un cluster
lorsque tous les autresmessages entrants sont arrivés
( , )m u r
![Page 26: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/26.jpg)
x7
x1 x2
x5x4 x6
x3
x5 x6
x8
x2 x3
x5 x6
x9x8
u
r
vp
w
Cluster Tree Elimination
( , )m u r
( , )m p v
( , )m w r
![Page 27: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/27.jpg)
x7
x1 x2
x5x4 x6
x3
x5 x6
x8
x2 x3
x5 x6
x9x8
u
r
vp
w
Cluster Tree Elimination
( , )m p v
( , )m w r( , )m u r
( , )m v r
![Page 28: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/28.jpg)
x7
x1 x2
x5x4 x6
x3
x5 x6
x8
x2 x3
x5 x6
x9x8
u
r
vp
w
Cluster Tree Elimination
( , )m p v
( , )m u r ( , )m w r
( , )m v r
Temps: (n.exp(w))Espace: (n.exp(s)) s : taille du plus grand séparateur
![Page 29: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/29.jpg)
x7
x1 x2
x5x4 x6
x3
x5 x6
x8
x2 x3
x5 x6
x9x8
u
r
vp
w
BTD (Terrioux & Jégou, 2003)Backtrack with Tree Decomposition
Ordre d’affectation desvariables du cluster racineaux clusters fils
u, w, (v & p) résolus indépendamment.Ils ne dépendent que de r.
Temps : (exp(h))Espace : (n) h : hauteur d’arbre
Hybridation recherche et décomposition arborescente
![Page 30: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/30.jpg)
x7
x1 x2
x5x4 x6
x3
x5 x6
x8
x2 x3
x5 x6
x9x8
u
r
vp
w
Mémorise l’optimumde chaquesous-problème(majorant initial = ++))
Opt(u[A])
Opt(w[A])
Opt(p[A])
Opt(v[A])
BTD (Terrioux & Jégou, 2003)
Temps: (n.exp(w))Espace: (n.exp(s))
![Page 31: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/31.jpg)
x7
x1 x2
x5x4 x6
x3
x5 x6
x8
x2 x3
x5 x6
x9x8
u
r
vp
w
Amélioration du majorant local: BTD+
Soit solution trouvée Optimum prouvéSoit pas de solution
Minorant seulement!
LB(A[p]) = UBp
Théo.: répétition bornée
UBp UBr – Cost(A,r)
– Cost(A,v)
– Opt(A[u])
– Opt(A[w])
Temps: (UBr.n.exp(w))Espace: (n.exp(s))
![Page 32: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/32.jpg)
Introduction aux cohérences locales souples
But: transformer un problème en un problème équivalent dont le minorant soit plus explicite
Établir des propriétés de cohérence locale par des opérations de déplacement des coûtscontrainte binaire contrainte unaire contrainte zéro W
(minorant)
0 0
0 0
0
0
0
0
0
0
X1 X2 X3 X4 X5
W=0
GUB=2
a
b
Hybridation recherche, propagation et décomposition
![Page 33: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/33.jpg)
Introduction aux cohérences locales souples
0 0
0 0
0
0
0
0
0
0
X1 X2 X3 X4 X5
W=0
GUB=2
AC (Schiex, 2000)
projection
a
b
![Page 34: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/34.jpg)
Introduction aux cohérences locales souples
0 0
0 0
0
0
0
11
0
0
X1 X2 X3 X4 X5
W=0
GUB=2
AC (Schiex, 2000)
projection
a
b
![Page 35: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/35.jpg)
Introduction aux cohérences locales souples
0 0
0 0
0
0
0
1
0
0
X1 X2 X3 X4 X5
W=0
GUB=2
AC (Schiex, 2000)
a
b
projections
![Page 36: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/36.jpg)
Introduction aux cohérences locales souples
0 11
0 11
0
0
0
1
0
0
X1 X2 X3 X4 X5
W=0
GUB=2
AC (Schiex, 2000)
a
b
![Page 37: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/37.jpg)
Introduction aux cohérences locales souples
0 11
0 11
0
0
0
1
0
0
X1 X2 X3 X4 X5
W=0
GUB=2
NC* (Larrosa, 2002)
a
b
projection
![Page 38: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/38.jpg)
Introduction aux cohérences locales souples
0 0
0 0
0
0
0
1
0
0
X1 X2 X3 X4 X5
W= 11
GUB=2
NC* (Larrosa, 2002)
a
b
![Page 39: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/39.jpg)
Introduction aux cohérences locales souples
0 0
0 0
0
0
0
11
0
0
X1 X2 X3 X4 X5
W= 11
GUB=2
NC* (Larrosa, 2002)
Suppressionde valeur
a
b
![Page 40: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/40.jpg)
Introduction aux cohérences locales souples
0 0
0 0
0
0
0 0
0
X1 X2 X3 X4 X5
W= 11
GUB=2
NC* (Larrosa, 2002)
a
b
![Page 41: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/41.jpg)
Introduction aux cohérences locales souples
0 0
0 0
0
0
0 0
0
X1 X2 X3 X4 X5
W= 1
GUB=2
NC* (Larrosa, 2002)
a
b
![Page 42: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/42.jpg)
Introduction aux cohérences locales souples
0 0
0 0
0
0
0 11
0
X1 X2 X3 X4 X5
W= 1
GUB=2
NC* (Larrosa, 2002)
a
b
![Page 43: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/43.jpg)
Introduction aux cohérences locales souples
0 0
0 0
0
0
0
0
X1 X2 X3 X4 X5
W= 1
GUB=2
NC* (Larrosa, 2002)
a
b
![Page 44: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/44.jpg)
Hiérarchie
NC* O(nd)
AC* O(n 2d 3) DAC* O(ed 2)
FDAC* O(end 3)AC
NC
DAC
Cas spécial : CSP (T=1)
d : taille du plus grand domainee : nombre de contraintes
EDAC O(ed2.max(UB,nd))(ijcai 2005)
![Page 45: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/45.jpg)
BT
MNC
MAC/MDAC
MFDAC
MEDAC
![Page 46: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/46.jpg)
x7
x1 x2
x5x4 x6
x3
x5 x6
x8
x2 x3
x5 x6
x9x8
u
r
vp
w
Lc-BTD+ : BTD+ avec cohérence locale souple
Mouvements de coûtsinvalident les minorants
mémorisésW= 1
GUB=2Une augmentation de
W peut avoir un impact
sur n’importe quel cluster pas de garantie detrouver l’optimum d’un
sous problème
![Page 47: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/47.jpg)
Trois approches possibles
Propagation restreinte à l’intérieure de chaque cluster
Backward Checking et Forward Checking
e.g. FC-BTD (Terrioux&Jégou, 2003)
Propagation restreinte à l’intérieure de chaque sous problème
Lc-BTD+ Lc-BTD+ (de Givry et al., 2005)
Propagation sans aucune restriction
Lc-BTD* Lc-BTD* (de Givry et al., 2005)
![Page 48: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/48.jpg)
Lc-BTD*Lc-BTD*
Suppression de valeurs Coupe locale : WXi(a) + ∑Cj descend. of CkCkW
Cj UBk Coupe globale : WXi(a) + ∑Cj descend. of C1C1W
Cj GUB
Idée: collecter des minorants et majorantsà tous les nœuds de la frontière d’exploration de l’arbre de recherche
Répétition non bornée Temps: (exp(h)) Espace: (n.exp(s))
OptimumNouvelle solution
Frontière
![Page 49: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/49.jpg)
Trois approches possibles
Méthode Complexité temps Complexité espace
Lc-BTD (n.exp(w)) (n.exp(s))
Lc-BTD+ (GUB.n.exp(w)) (n.exp(s))
Lc-BTD* (exp(h)) (n.exp(s))
GUB = majorant globaln = nombre de variablesh = hauteur d’arbre w = largeur d’arbres = taille séparateur maximale
s w h n
![Page 50: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/50.jpg)
Résultats expérimentaux
Still-Life
DIMACS (SAT)
Arbres de cliques aléatoires
Allocation de fréquences CELAR
Réseaux Bayésiens (MPE)
![Page 51: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/51.jpg)
Still-Life (problème académique)
Instance: n=14#variables:196 , #valeurs:2
CP / IP (Ilog Solver) (Bosch&Trick 2002) 5 jours
Variable Elimination (Larrosa 2003) 1 jour
DFBB-VE(2) (Larrosa 2005) 2 secondes
![Page 52: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/52.jpg)
DIMACS (SAT)
Problem (n,c,w,h) MFDAC MFDAC-VE(2) FDAC-BTD+ VEaim-100-1_6-no-1 (100,160,42,52) - 1853.16 - -aim-100-1_6-no-2 (100,160,42,51) 3139.6 400.33 - -dubois20 (60,160,3,33) 25.72 37.5 0.01 0dubois100 (300,800,3,153) - - 0.13 0hole06 (42,133,27,33) 0.07 0.06 0.08 89.86hole08 (72,297,45,57) 9.85 9.86 27.25 -pret60_25 (60,160,6,18) 74.12 34.51 0.02 0pret150_25 (150,400,9,23) - - 0.12 0bf0432-007 (1040,3668,117,177) 754.92 210.17 - -bf2670-001 (1393,3434,27,72) - - 2705.61 20.47ssa0432-003 (435,1027,22,44) 2.57 0.92 1.08 0.3ssa2670-141 (986,2315,23,54) - 907.1 28.73 1.18
![Page 53: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/53.jpg)
Arbres de cliques aléatoires
Résultats identiques entre FDAC-BTD+ et FDAC-BTD*
FDAC-BTD+
FC-BTD
FC-BTD+
NC-BTD-BJ+
FDAC-BTD-BJ+
FC-BTD
FC-BTD+, NC-BTD-BJ+
FDAC-BTD-BJ+FDAC-BTD+
• Décomposition arborescente avec heuristique Maximum Cardinality Search• Ordre choix variable domain/degree compatible avec la décomposition• Répétition dans BTD+ : moyenne ≤ 2.6, maximum = 14
![Page 54: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/54.jpg)
Allocation de fréquences (CELAR SCEN06)
![Page 55: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/55.jpg)
Allocation de fréquencesBut: Affectation de fréquences à des liens radio de telle sorte que les liens
fonctionnent sans interférences notables (Cabon et al., 1999)
SUBCELAR1 SUBCELAR3 SCEN-06-24r SCEN-07-104-30r
n=14, d=44w=9, h=14
n=18, d=44w=12, h=15
n=99, d=20w=10, h=37
n=196, d=14w=12, h=32
time space time space time space time space
FC-BTD 7,489 4,344 23,560 69,808 -* 3,002,547 - 109,311,451
NC-BTD-BJ+ 2,647 4,344 11,342 9,024 9,231 6,326,854 38 (5) 83,557
FDAC-BTD-BJ+ 66 0 653 0 4,789 65,270 15 (3) 5,874
FDAC-BTD-BJ* 65 0 638 0 4,573 64,571 30 (12) 9,247
MFDAC 14 0 193 0 - 0 - 0
* - : Time limit of 10 hours exhausted or 4 billion nodes expanded
Tree decompositionwith min degree heur.2-sided Jeroslow DVO
(rep.)
![Page 56: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/56.jpg)
Réseaux bayésiens (MPE)
Problem (n,d,w,h) MFDAC FDAC-BTD+ VE s-AOMB(5)barley (48,67,7,16) 4.39 1.52 7.86 0.56cpcs360b (360,2,20,26) 0.09 0.1 4.03cpcs422b (422,2,23,37) 0.45 0.13 20.04diabetes (413,21,5,43) - 1548.11 0.77link (724,4,17,41) - 1595.43 8.11mildew (35,100,4,13) 0.24 0.14 1.12 0.66munin1 (189,21,11,23) 0.3 0.9 37.79 1.66munin2 (1003,21,8,26) - 22.48 0.43 1.64munin3 (1044,21,7,22) - 27.88 0.4 0.45munin4 (1041,21,8,27) - 132.75 3.45pigs (441,3,11,24) - 9.35 0.15 0.02
Ordres d’élimination : min-degree(FDAC-BTD+), min-fill(VE,s-AOMB)s-AOMB (Dechter & Marinescu, 2005)
![Page 57: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/57.jpg)
Conclusion
![Page 58: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/58.jpg)
Comparaison des méthodes
Méthodes DVO Propa. Complexité en temps
Complexité en espace
DFBB oui oui (exp(n)) (n)
VE non non (n.exp(w)) (n.exp(w))
DFBB-VE(k) oui oui Inférieure à (exp(n))
(n.exp(k))
CTE non non (n.exp(w)) (n.exp(s))
Lc-BTD non oui (n.exp(w)) (n.exp(s))
Lc-BTD+ non oui (GUB.n.exp(w)) (n.exp(s))
Lc-BTD* non oui (exp(h)) (n.exp(s))
s ≤ w ≤ h ≤ n
![Page 59: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/59.jpg)
Compromis temps/mémoire paramétrable
Méthodes Complexité en temps
Complexité en espace
DFBB (exp(n)) (n)
VE (n.exp(w)) (n.exp(w))
DFBB-VE(k) Inférieure à (exp(n))
(n.exp(k))
CTE (n.exp(w)) (n.exp(s))
Lc-BTD(k) (n.exp(w’)) (n.exp(k))
Lc-BTD+(k) (GUB.n.exp(w’)) (n.exp(k))
Lc-BTD*(k) (exp(h)) (n.exp(k))
s ≤ w ≤ w’ ≤ h ≤ n
Cache uniquement pour des tailles de séparateur ≤ k
![Page 60: Méthodes hybrides dans les réseaux de contraintes pondérées Simon de Givry, Thomas Schiex, INRA Toulouse Gérard Verfaillie, Sylvain Bouveret, ONERA Toulouse](https://reader035.vdocumento.com/reader035/viewer/2022062417/551d9d81497959293b8bb604/html5/thumbnails/60.jpg)
toolbar, toulbar2 et site Web interactif
Librairie open source Accessible depuis un wiki
http://carlit.toulouse.inra.fr/cgi-bin/awki.cgi/SoftCSP Implémente NC,AC,DAC,FDAC,EDAC et BAC Implémente DFBB, VE, DFBB-VE(2) et Lc-BTD+ Lecture des formats Max-CSP wcspwcsp, Max-SAT cnfcnf (avec
ou sans pondérations) et réseaux bayésiens MPE ergoergo Nombreux benchmarks dans des formats standardisés Source forge à
http://mulcyber.toulouse.inra.fr/projects/toolbar/http://mulcyber.toulouse.inra.fr/projects/toulbar2/