ch3et4

8/7/2019 ch3et4

1/53

Chapitre 3

Une methode de decomposition par lasubstituabilite directionnelle pour lesCSPs Valuees

Resume

La notion de substituabilite directionnelle est une forme faible de la substituabilite de voisi-nage [10] qui a ete proposee dans [24] pour ameliorer la resolution des problemes de satisfaction decontraintes (CSPs) binaires. On part du fait que meme si deux valeurs ne sont pas voisinage sub-stituables, elles peuvent letre si on restreint le voisinage en se referant a un ordre sur les variables.La substituabilite directionnelle permet de decomposer les domaines de valeurs des variables ende sous-ensembles de valeurs qui peuvent etre essayees simultanement lors de la resolution duprobleme par un algorithme du type Backtracking.

Dans le present chapitre, nous proposons les extensions suivantes au travail presente dans [24] :

Tout dabord, nous generalisons davantage la notion de substituabilite directionnelle en

considerant, comme reference, une orientation du graphe dinconsistance au lieu dun ordresur les variables.

Pour garantir loptimalite de la solution lors de la resolution des Problemes de Satisfactionde Contraintes Valuees a contraintes binaires fixes (VCSPs a contraintes binaires fixes),nous introduisons des conditions supplementaires de substituabilite.

Ensuite, nous generalisons davantage la notion dinterchangeabilite directionnelle en consi-derant, comme reference, une orientation du graphe dinconsistance au lieu dun ordre surles variables.

Pour garantir loptimalite de la solution lors de la resolution des Problemes de Satisfactionde Contraintes Valuees (VCSPs), nous introduisons des conditions supplementaires din-

40

8/7/2019 ch3et4

2/53

Chapitre III : Une methode de decomposition par la substituabilite directionnelle pour lesVCSPs

terchangeabilite.

En fin, nous exploitons la notion de substituabilite directionnelle proposee pour les VCSPsa contraintes binaires fixes pour resoudre les VCSPs

Comme le dual dun VCSP est un VCSP a contraintes binaires fixes. Il suffit de transfor-mer le VCSP en VCSP a contraintes binaires fixes en passant par son dual et appliquer lamethode de decomposition par la substituabilite directionnelle.

Des resultats de simulation, sur plusieurs VCSPs et VCSPs a contraintes binaires fixes modeli-sant des problemes dordonnancement, montrent que des variantes de lalgorithme du Branch-and-Bound qui exploitent la substituabilite directionnelle sont souvent plus efficace que lalgorithmeoriginal.

**********************************************************************Methodes de decomposition de domaines pour les CSPs Values

**********************************************************************41

8/7/2019 ch3et4

3/53


3.1 Introduction

Dans ce chapitre nous nous interessons aux methodes de resolution de VCSPset de VCSPs a contraintes binaires fixes (VCSP-FbC) dites completes : cellesqui permettent de trouver une solution optimale si cette derniere existe. Sinon, trouver la solution qui viole le minimum des contraintes.

Lalgorithme du Branch-and-bound [20] est sans doute lalgorithme com-plet le plus utilise pour resoudre les VCSPs a contraintes binaires fixes. Cestune procedure dexploration en profondeur dabord munie dune fonction heu-

ristique servant a evaluer le cout de la solution complete que lon peut espereratteindre par lextension de la solution partielle courante. Le role de la fonc-tion heuristique est deviter lexploration de branches de larbre de recherchequi ne menent pas a des solutions meilleures que celles deja trouvees.

Par ailleurs, la notion de substituabilite de voisinage [10] a ete proposee etutilisee comme un moyen de filtrage des domaines de valeurs des variables desCSPs binaires. Plusieurs variantes de cette notion ont ete proposees, parmi

lesquelles la notion substituabilite directionnelle [24].

Cette derniere est une forme faible de la substituabilite de voisinage qui, audepart, visait a ameliorer la resolution des CSPs binaires.

On part de lidee que meme si deux valeurs ne sont pas voisinage substi-tuables, elles peuvent letre si on restreint le voisinage en se referant a unordre sur les variables. La substituabilite directionnelle ne peut pas etre uti-lisee comme un moyen de filtrage des domaines des variables comme cest lecas pour la substituabilite de voisinage.

Toutefois, on peut lutiliser comme un moyen de decomposition des domainesdes variables en de chaines de valeurs directionnellement substituables quipeuvent etre considerees simultanement lors de la resolution de problemes.

Dans le present chapitre, nous proposons une methode de resolution ba-see sur la substituabilite directionnelle pour les VCSPs a contraintes binaires

fixes. Les divers etapes de cette methode sont presentees dans la figure 3.1.


**********************************************************************42

8/7/2019 ch3et4

4/53


FbC

FbCFbC FbC 1

FbC 2

FbC nc

FbC i

FbC

Figure 3.1 Les etapes de la Methode de decomposition de domaine pour les VCSPsFbC

Nous proposons, ensuite, une methode de resolution basee sur linterchan-geabilite directionnelle pour le cadre generale : les VCSPs binaires. Les diversetapes de cette methode sont presentees dans la figure 3.2.

En effet, dans ce chapitre, nous proposons les extensions suivantes du travailpresente dans [24] :

Tout dabord, nous generalisons davantage la notion de substituabi-lite directionnelle en considerant, comme reference, une orientation dugraphe dinconsistance au lieu dun ordre sur les variables.

Pour garantir loptimalite de la solution lors de la resolution des Pro-blemes de Satisfaction de Contraintes Valuees a contraintes binaires fixes

(VCSPs a contraintes binaires fixes), nous introduisons des conditionssupplementaires de substituabilite.


**********************************************************************43

8/7/2019 ch3et4

5/53


1

2

nc

i

Figure 3.2 Les etapes de la Methode de decomposition de domaine pour les VCSPsFbC

Ensuite, nous generalisons davantage la notion dinterchangeabilite di-rectionnelle en considerant, comme reference, une orientation du graphedinconsistance au lieu dun ordre sur les variables.

Pour garantir loptimalite de la solution lors de la resolution des Pro-blemes de Satisfaction de Contraintes Valuees (VCSPs), nous introdui-sons des conditions supplementaires dinterchangeabilite.

En fin, nous exploitons la notion de substituabilite directionnelle propo-see pour les VCSPs a contraintes binaires fixes pour resoudre les VCSPs

Comme le dual dun VCSP est un VCSP a contraintes binaires fixes. Il

suffit de transformer le VCSP en VCSP a contraintes binaires fixes enpassant par son dual et appliquer la methode de decomposition par la


**********************************************************************44

8/7/2019 ch3et4

6/53


substituabilite directionnelle.

Ce chapitre est organise comme suit : dans la section 3.2, nous donnonsles definitions et les notations utilisees.

Nous definissons par la suite (section 3.3), la notion de substituabilite direc-tionnelle. On presente, dans la meme section, une version de lalgorithme duBranch-and-Bound qui exploite la substituabilite directionnelle ainsi quunalgorithme qui decompose les domaines de valeurs en de chanes de valeursdirectionnellement substituables.

Ensuite Nous definissons (section 3.4), la notion dinterchangeabilite direc-tionnelle etendue. On presente, dans la meme section, une version de lalgo-rithme du Branch-and-Bound qui exploite linterchangeabilite directionnelleetendue ainsi quun algorithme qui decompose les domaines de valeurs en desclasses de valeurs equivalentes.

La section 3.5 presente un algorithme dorientation du graphe dinconsistance

utilisee dans la determination de la substituabilite directionnelle.

Dans la section 3.7, nous reportons les resultats dune experimentation mon-trant lapport de lexploitation de la notion de substituabilite directionnellepour la resolution de VCSPs binaires.

3.2 Definitions et notations

Definition 13 Une fonction objective est definie comme suit :P(t) =

cC c(t[(c)])

Larite dune contrainte est la taille de sa portee. Larite dun problemeest larite maximale de ses contraintes. Deux variables xi et xj reliees par unecontrainte binaire, notee Ci,j, sont dites voisines. La valeur a Di, denoteeaussi (xi, a), est compatible avec b Dj si (a, b) Rel(Ci,j). Dans ce cas, ondit que b est un support de a. Si chaque valeur du probleme a, au moins, unsupport dans le domaine de chaque variable voisine alors le probleme est dit

arc-consistant.


**********************************************************************45

8/7/2019 ch3et4

7/53


Le graphe dinconsistance dun VCSP binaire est un graphe simple danslequel les sommets correspondant aux valeurs des variables et les aretes relientles couples de sommets qui representent des valeurs incompatibles. Lensembledes valeurs incompatibles avec une valeur a dune variable xi, est defini par

N(xi, a) = {(xj, b) | Ci,j C et i,j(a, b) = ((a, b) / Rel(Ci,j))}

En se referant a [10], une valeur a dune variable xi est voisinage substituable(VS) a une valeur b de xi si et seulement si

N(xi, a) N(xi, b) ( a Xj) i,j(a, a) i,j(b, a)

(Xj est lensemble de variables voisines a xi).

Cette definition peut etre etendue pour tenir compte de la fonction cout.Toutefois, cette derniere doit verifier certaines proprietes pour que ceci soitpossible.

En effet, la fonction cout est une fonction globale (n-aire) puisquelle sap-plique a toutes les variables du probleme (voir definition 9) alors que la notionde substituabilite de voisinage est une notion locale. On propose donc que soit une fonction telle quil est possible de trouver une fonction cout unairei :

ni=1 Di E qui verifie

T D1 . . . Dn, (T) = ni=1i(Ti) (3.1)

ou designe un operateur monotone sur E et Ti la valeur affectee a la

variable xi dans T. La substituabilite de voisinage pour les VCSPs binaires acontraintes binaires fixes peut alors etre definie de la maniere suivante :

a P b

i,j(a, a) i,j(b, a) ( a Xj)

eti(a) i(b)

Il en decoule qua partir de toute solution dans laquelle xi a pour valeur b, onpeut deduire une solution de qualite, au moins, egale si lon substitue a a b.

Par consequent, b peut etre supprimee du domaine de xi sans que lon perdetoutes les solutions optimales du probleme.


**********************************************************************46

8/7/2019 ch3et4

8/53


3.3 Substituabilite directionnelle (DS) pour les VCSPs

a contraintes binaires fixes3.3.1 Definitions et proprietes

La substituabilite directionnelle [24] est une forme faible de substituabilitede voisinage. Au depart, cette notion a ete definie en se referant a un ordretotal sur les variables du probleme.

Dans le present chapitre, on generalise la notion de substituabilite direction-

nelle en utilisant, comme reference, une orientation du graphe dinconsistancedu VCSP a contraintes binaires fixes. Formellement, une orientation dugraphe dinconsistance dun VCSP a contraintes binaires fixes est une affec-tation dune direction a chaque arete {a, b} du graphe donnant lieu, ou biena larc (a, b) ou bien a larc (b, a).

Etant donnee une orientation du graphe dinconsistance dun VCSP acontraintes binaires fixes, on definit lensemble des conflits directionnels dunevaleur a dune variable x

ipar rapport a de la maniere suivante :

N(xi, a) = {(xj, b) | Ci,j C et i,j(a, b) =

((a, b) / Rel(Ci,j) et(a, b) )} (3.2)

La substituabilite directionnelle est alors definie comme suit :

Definition 14 Soit P = (X,D,C,S) est un VCSP binaire a contraintes bi-naires fixes.soit a et b sont 2 valeurs de xi et a est une valeur de Xj Ni dans P.

a P b

i,j(a, a) i,j(b, a) ( a Xj)

eti(a) i(b)

Exemple 13 Seulement dans la Figure 3.3(a) les deux conditions de la definition 14 sont verifiees, dou a P b. Alors que dans la Figure 3.3(b)i,j(a, a) i,j(b, a) et dans la Figure 3.3(c) i(a) i(b)


**********************************************************************47

8/7/2019 ch3et4

9/53


Figure 3.3 Quand est ce que a P b ?

Dans ce qui suit, on utilisera la notation au lieu de P si ceci nentraine

pas dambigute. La relation definit un preordre sur le domaine de chaquevariable. Ainsi, chaque domaine Di peut etre subdivise en de sous-ensemblesDi = Di,1 . . . Di,s tel que les elements de chaque Di,k, k = 1,...,s sonttous deux a deux comparables. Cest-a-dire, que pour tout a, b Di,k, on a

a b ou b a. Chaque Di,k est donc une chaine de valeurs totalementordonnee par .

Dans chaque chaine Di,k, on peut distinguer le sous-ensemble des elementsminimaux.

min(Di,k) = {a Di,k | b Di,k, a b} (3.3)

La proposition suivante identifie une classe polynomiale de VCSPs a contraintesbinaires fixes.


**********************************************************************48

8/7/2019 ch3et4

10/53


Propriete 1 Soit P = (X,D,C,S) un VCSP binaire a contraintes binaires fixes arc-consistant et soit est une orientation du graphe dinconsistancede P. Si chacun des domaines de valeurs de P est une chaine non vide devaleurs directionnellement substituables par rapport a alors une solutionoptimale de P peut etre trouvee en un temps polynomial.

Preuve 1 On montre quen selectionnant un element minimum de chaquedomaine de valeur, on obtient une solution optimale. Ce qui veut dire quetout n-uplet T min(D1) . . . min(Dn) est une solution optimale. En sereferant a (??) et au fait que la fonction i est calculable en temps polyno-

mial, cette selection peut etre effectuee en temps polynomial.

Supposons que T min(D1) . . . min(Dn) nest pas une solution optimale.Ceci implique que T est inconsistant ou que (T) nest pas minimum.

Commencons par supposer que T est inconsistant. Donc T doit contenir, aumoins, une paire de valeurs incompatibles. Soit a min(Di) et b min(Dj)une telle paire. Puisque a et b sont incompatibles, on doit avoir (a, b) ou(b, a) .

Supposons, sans perte de generalite, que (a, b) , (sinon on pourra rai-sonner sur b au lieu de a et obtenir le meme resultat). Il sen suit queb N(xi, a), et puisque a min(Di) alors pour tout a Di, on doit avoirb N(xi, a). Ce qui veut dire que b na pas de support dans Di et donc queP nest pas arc-consistant, dou une contradiction.

Supposons, a present que (T) nest pas minimum, donc, quil existe T

D1 . . . Dn tel que (T) < (T). Puisque les valeurs de la fonction (T)sont obtenues a partir de celles de i(Ti) en utilisant un operateur monotone(voir equation (3.1)), il doit exister xi X tel que Ti = (xi, a), Ti = (xi, a

)eti(xi, a

) < i(xi, a). Il en resulte que a / min(Di), dou une contradiction.

Nous nous interessons aux methodes de resolution de VCSPs a contraintesbinaires fixes dites completes : celles qui permettent de trouver une solutionoptimale si cette derniere existe. Sinon trouver la solution qui viole le mini-

mum de contraintes.


**********************************************************************49

8/7/2019 ch3et4

11/53


Lalgorithme du Branch-and-bound est lalgorithme complet le plus commu-nement utilise pour resoudre les VCSPs a contraintes binaires fixes. Cet al-gorithme explore lespace de recherche du probleme a resoudre en effectuantune recherche arborescente en profondeur dabord.

Les problemes consideres tout lelong dun chemin de larbre de recherchesont des reductions du probleme initial que lon peut definir de la manieresuivante :

Definition 15 Un probleme P = (X,D,C,S) est une reduction dun pro-

bleme P = (X, D, C, S) (notation P P) si et seulement si X = X, Di D

i, pour tout xi X,

C = {Ci,j | Ci,j C et Rel(Ci,j) = Rel(C

i,j) Di Dj},

S est la restriction de S a D1 . . . Dn.

Une propriete essentielle de la substituabilite directionnelle est quelle soitpreservee quand on passe dun probleme a lune de ses reductions. Formelle-ment, on a

Propriete 2 Soient P = (X,D,C,S) et P = (X, D, C, S) deux VCSPsbinaires a contraintes binaires fixes tel que P P et soit , (resp. ) uneorientation du graphe dinconsistance de P (resp. de P) telle que .Alors, on a

xi X, a, b Di Di, a

P

b a P b

Preuve 2 Designons par NP(xi, a) lensemble des conflits directionnels de

(xi, a) dans P et par D lensemble des valeurs de P qui ne figurent pasdans P. On a donc D =

xiX D

i Di. Soient (xi, a) et (xi, b) deux valeurs

quelconques disponibles dans P et P. Puisque P P, on a

NP(xi, a) = NP(xi, a) D (3.4)

De meme

NP(xi, b) = NP(xi, b) D (3.5)


**********************************************************************50

8/7/2019 ch3et4

12/53


Dautre part, en partant de a P

b, on deduit que NP(xi, a) D

N

P

(xi, b) D et que i(xi, a) i(xi, b). Dapres (3.4) et (3.5), on ob-tient NP(xi, a) NP(xi, b). Dou, a P b.

Une consequence directe de la proposition 2 est que pour toute paire deVCSPs a contraintes binaires fixes P et P telles que P P, si Di est unechaine de valeurs DS dans P alors Di est une chaine de valeurs DS dans P.

3.3.2 Exemple

Exemple 14 Considerons le probleme Job-Shop classique decrit dans la fi-gure 3.4. Il sagit de planifier lexecution de deux jobs J1 et J2 sur troismachines M1, M2 et M3. Chaque job Ji se compose de trois taches Ti,1, Ti,2 etTi,3. Une tache Ti,j est dediee a etre executee sur la machine Mj.

Pour cet exemple, on suppose que la duree de toutes les taches est fixee a uneunite de temps, sauf T2,2 qui consomme deux unites. Les job-shops font inter-venir deux types de contraintes : des contraintes de precedence qui imposentque les taches dun meme job soient executees les une apres les autres ainsique des contraintes de ressource qui empechent quune machine execute plusdune tache a la fois.

Resoudre un tel probleme revient a affecter un temps de debut dexecution achacune des taches de facon a satisfaire les contraintes de precedence et deressource toute en minimisant le temps total dexecution de toutes les taches(makespan).

Une modelisation possible des problemes job-shops en termes de VCSP bi-naire a contraintes binaires fixes consiste a associer une variable du VCSPa contraintes binaires fixes a chacune des taches. Ainsi, pour notre exemple,on obtient un probleme impliquant six variables x1, . . . , x6.

Les domaines de valeurs des variables representent une discretisation dutemps maximum impartie a lexecution de toutes les taches. Pour le pre-

sent exemple, on suppose que les differentes taches peuvent commencer a des


**********************************************************************51

8/7/2019 ch3et4

13/53


instants representes par les entiers de 0 a 4.

Les contraintes impliquees sont des contraintes binaires de precedence et deressource. On en trouve en tout sept contraintes (voir figure 3.4). La fonctioncout a minimiser est celle definie par

(T) = max1i6

{a + duree(xi) | Ti = (xi, a)}

ou T designe une instanciation de toutes les variables du VCSP a contraintesbinaires fixes. En tenant compte des contraintes de precedence, la fonction

peut etre calculee en prenant le maximum uniquement sur la paire {x3, x6}au lieu de X.

On en deduit une definition possible de la fonction i

i(xi, a) =

a + duree(xi) si i {3, 6}0 sinon

(3.6)

On obtient donc (T) = max6i=1(i(Ti)), ou max est bien un operateur mo-

notone.Apres application dun algorithme darc-consistance, on obtient le pro-bleme dont le graphe dinconsistance est represente dans la figure 3.5. Danscette meme figure on peut egalement voir une orientation du graphe dincon-sistance.

En se referant a cette orientation, on obtient les ensembles des conflits direc-tionnels donnes dans le tableau 3.1.

En examinant ce tableau, on constate que tous les domaines de valeurs sontdes chaines de valeurs DS saufD2 qui est compose de deux chaines : {(x2, 1), (x2, 2)}et{(x2, 3)}. En reduisant le domaine de x2 a{(x2, 1), (x2, 2)} puis a{(x2, 3)},on obtient deux sous-problemes qui, dapres la proposition 2, ne contiennentque des chaines de valeurs DS comme domaine. Dapres la Propriete 1, cestdeux sous-problemes peuvent etre resolus en un temps polynomial.


**********************************************************************52

8/7/2019 ch3et4

14/53


T1,1 T1,2

T2,1 T2,2 T2,3

T1,3

contrainte de resource

contrainte de prcdence

J2

J1

Figure 3.4 Un probleme du type job-shop comportant deux jobs et six taches. Toutesles taches sont supposees avoir une duree dune unite de temps, sauf T2,2 qui en consommedeux.

3.3.3 Exploitation de la Substituabilite Directionnelle

La notion de substituabilite directionnelle peut etre utilisee pour ameliorer laresolution de VCSPs binaires a contraintes binaires fixes et ceci en lintegranta lalgorithme du Branch-and-Bound pour obtenir lalgorithme BABDS (voirfonction 2). Pour avoir une methode de resolution plus efficace, BABDS in-tegre egalement une procedure qui permet de maintenir larc-consistance du-rant la recherche comme dans lalgorithme de resolution de CSP MAC [29].

BABDS prend comme parametres le VCSP a contraintes binaires fixes a re-soudre (X,D,C,S), (qui est suppose etre arc-consistant), une orientation dugraphe dinconsistance du probleme , lensemble des variables non encoreinstanciees Y et la meilleure solution courante I et procede comme suit :il selectionne une variable non encore instanciee, calcule la partition de sondomaine de valeurs en des chaines de valeurs DS et decompose le problemecourant en deux sous-problemes.

Le premier sous-probleme est obtenu en reduisant le domaine de valeurs dela variable courante a une chaine de valeurs DS (notee Di,k dans le pseudo-

code). Larc-consistance du probleme resultant est alors restaure en utilisant


**********************************************************************53

8/7/2019 ch3et4

15/53


2

1

x1 x2

x4 x5 x6

x3

3

2

1

2

1 4

3

4

3

1

0

0

Figure 3.5 Graphe dinconsistance du job-shop decrit dans la figure 3.4 apres applica-tion dun algorithme darc-consistance. On peut egalement voir une orientation du graphedinconsistance.

un algorithme darc-consistance. Puis, un appel recursif est effectue pourconsiderer les variables restantes. Cet appel permet dobtenir la meilleure so-lution du sous-probleme qui limite les valeurs possibles de la variable couranteaux elements de Di,k.

Ensuite, un processus de restauration des domaines de valeurs est effectueet Di,k est eliminee du domaine de la variable courante. Apres restauration

de larc-consistance du probleme resultant, lalgorithme effectue un deuxiemeappel recursif pour considerer les autres chaines de valeurs DS.

Les deux appels recursifs ne sont effectues que si une fonction heuristique(h) indique quil est possible dobtenir des solutions de qualite meilleures quecelles deja trouvees. Si lalgorithme reussit a instancier toutes les variablesalors il execute un processus polynomial (ligne 1) pour extraire la meilleuresolution a partir des chaines selectionnees.


**********************************************************************54

8/7/2019 ch3et4

16/53


AlgorithmBABDS((X,D,C,S), , Y , I )

if Y = then1 retourner(min(D))

elsexi Select(Y)Di DS-Partition(Di, , (X,D,C,S))Di,k Select (Di)Di Di,kAC(X,D,C,S)if / D et h(D) < (I) then

I BABDS(Y {xi}, (X,D,C,S), , I)

if (I) < (I

) thenI I

Restaurer (D)Di Di - Di,kAC(X,D,C,S)if / D et h(D) < (I) then

I BABDS(Y {xi}, (X,D,C,S), , I)if (I) < (I) then

I I

Restaurer(D)

retourner(I)


**********************************************************************55

8/7/2019 ch3et4

17/53


0 1 2 3 4x1 (x4, 0)

x2 (x1, 1) (x1, 2) (x3, 3)(x1, 2) (x6, 3)

x3 x4 (x1, 1)

(x5, 1)x5 (x3, 3)

(x6, 3)x6

Table 3.1 Conflits directionnels des valeurs arc-consistantes du VCSP-FbC decrit dans lafigure 3.5.

3.3.4 Algorithme de DS partition

La relation definit un preordre sur le domaine de chaque variable duprobleme. Ce preordre peut etre utilise pour partitionner les domaines devaleurs des variables en de chaines de valeurs DS. En effet, a partir de ,on definit, tout dabord, la relation telle que a b si et seulement sia b et b a. On peut facilement verifier que est une relation dequi-valence. induit un ordre partiel sur lensemble Di\ des classesdequivalence de tel que [a] [b] si et seulement si a b, ou [a]designe la classe dequivalence de la valeur a.

En general, etant donne un ensemble partiellement ordonne E, on peut avoirplusieurs partitions de Een chaines delements totalement ordonnes. En theo-rie des ensembles, la partition optimale en chaines dun ensemble partielle-ment ordonne est connue sous le nom de partition en chaines de Dilworth

(DCP) [9].

Cest une partition qui contient le nombre minimum de chaines parmi toutesles partitions possibles. La taille dune telle partition (i.e., le nombre dechaines de la partition), definit la largeur de lordre partiel. Le problemequi consiste a trouver la DCP dun ensemble partiellement ordonne peut etreresolu en temps polynomial en lexprimant comme un probleme de recherchedun couplage maximum dans un graphe bipartite [13].

Motive par le fait qua chaque noeud de larbre de recherche, lalgorithme de


**********************************************************************56

8/7/2019 ch3et4

18/53


[a1] [b1] [k1]

BAB_DS

[a2] [b2] [k2]

[ai] [bi] [ki]

[an] [bn] [kn]

[1] [1] [1]

[2] [2] [2]

[] [] []

[] [] []

[1] [1] [1]

[2] [2] [2]

[] [] []

[] [] []

CSOP

_Chain

e_DS

_1

CSOP_Chaine_DS_i

CSOP_Chaine_DS_l

Figure 3.6 Decomposition dun VCSPFbC en de chaines de valeurs directionnellementsubstituables

resolution aura autant de choix que de chaines dans une DCP du domaine dela variable courante, nous proposons de calculer une DCP a chaque noeud delarbre de recherche. Par cette strategie, on cherche a minimiser la taille delarbre de recherche que lalgorithme aura a explorer.

La premiere etape du calcul de la DCP (voir la fonction 3) consiste a determi-ner la relation . Ceci peut etre accompli en O(nd

2) etapes en utilisant lal-gorithme decrit dans [10] ou celui propose dans [24]. On en deduit les classesdequivalences Di/ en O(d) etapes. Letape la plus couteuse est celle ducalcul de la relation . Au pire des cas, d(d 1)/2 tests dinclusion entredes paires densembles de conflits directionnels sont necessaires. Chaque testdinclusion peut etre accompli en O(nd) puisque chaque ensemble de conflitdirectionnel contient au maximum d(n 1) elements. Dou une complexite

de O(nd3) pour cette etape.


**********************************************************************57

8/7/2019 ch3et4

19/53


a

a

Figure 3.7 La partition en chaine de Dilworth (DCP)

Ensuite, lalgorithme construit un graphe bipartite G = (V, U, E ) tel queV = U = Di/ et lensemble des aretes E contient une arete ([a], [b]) si etseulement si [a] [b]. La construction de G necessite O(d

2) etapes. Un algo-rithme de couplage maximum est alors applique a G. On utilise lalgorithme

decrit dans [13] qui sexecute en O(d2.5) etapes.

Les chaines de la DCP sont extraites du couplage maximum en incluant leselements de [a] et ceux de [b] dans une meme chaine chaque fois que larete([a], [b]) fait partie du couplage maximum. Ceci demande O(d2) etapes. Douune complexite totale de O(nd3).


**********************************************************************58

8/7/2019 ch3et4

20/53


111 12 1k1

212 22 2k2

i1i i2 iki

n1n n2 nkn

Figure 3.8 Complexite de la partition en chaine de Dilworth

3.3.5 Exemple (suite)

Exemple 15 Reprenons lexemple du paragraphe 3.3.2. Comme on la dejaconstate, apres application dun algorithme darc-consistance, tous les do-maines de valeurs se trouvent reduits a des chaines de valeurs DS sauf D2qui est compose de deux chaines : {(x2, 1), (x2, 2)} et {(x2, 3)}.

Lapplication de lalgorithme BABDS a cet exemple se resume a instancierles variables x1, x3, x4, x5 et x6 par les seules chaines qui constituent leursdomaines respectifs. Pour x2, il y a deux instanciations possibles qui corres-pondent aux deux chaines donnees ci-dessus.

Commencons par reduire D2 a la chaine {(x2, 1), (x2, 2)}. A ce stade, tous lesdomaines sont des chaines de valeurs DS. La restauration de larc-consistance

(ligne 8) ne change rien a ce fait dapres la proposition 2. Le graphe dincon-


**********************************************************************59

8/7/2019 ch3et4

21/53


Algorithm DSPartition(Di, , (X,D,C,S)); DirInterchangeable (Di, , (X,D,C,S));

Di/ ExtractEqClass(, Di, (X,D,C,S)); DirSubstituable(Di/ , (X,D,C,Z));G BipartiteGraph(Di/ , );M CouplageMaximum(G);Di ExtractChaines(Di, , M);return(Di);

1

0

x1 x2

x4 x5 x6

x3

3

2

2

(b)

1

0

x1 x2

x4 x5 x6

x3

3

4

2

1

1

(a)

2

4

1 4

0

14

3

1

0

Figure 3.9 (a) Graphe dinconsistance du VCSP-FbC associe au job-shop decrit dans lafigure 3.4 apres reduction de D2 a la chaine {(x2, 1), (x2, 2)} et application dun algorithmedarc-consistance. (b) Graphe dinconsistance du meme VCSP-FbC apres reduction de D2 a

la chaine {(x2, 3)} et application dun algorithme darc-consistance.

sistance du probleme obtenu est illustre dans la figure 3.9-(a). Par la suite,lalgorithme choisit un element minimum de chacun des domaines (ligne 2).

Dapres le tableau 3.1 et la figure 3.9-(a), le choix est unique pour chacunedes variables et lon obtient linstanciation complete (1, 2, 3, 0, 1, 3) qui estbien une solution qui satisfait toutes les contraintes et qui a un cout egal a 4unites de temps.

Enfin, BABDS reduit D2 a {(x2, 3)}. En appliquant lalgorithme darc-consistance, puis la fonction heuristique h sur les domaines ainsi reduits,on deduit quil nest pas possible de trouver une solution meilleure que celledeja trouvee. En effet, les domaines de x3 et de x6 sont tous les deux reduitsa la seule valeur 4 (voir figure 3.9-(b)). Ce qui veut dire que la meilleuresolution quon peut esperer trouver a un cout de 5 unites de temps.


**********************************************************************60

8/7/2019 ch3et4

22/53


3.4 Interchangeabilite Directionnelle etendue pour les

VCSPs (EDI)3.4.1 Definitions et proprietes

Linterchangeabilite directionnelle etendue est une forme faible de linter-changeabilite de voisinage. Elle est definie en se referant a une orientationdu graphe de contraintes. Formellement, une orientation du graphe decontraintes est un sens de direction de chaque V ar(Cxi).

Etant donnee une orientation du graphe de contraintes, nous definissonslinterchangeabilite directionnelle etendue (EDI) pour les VCSPs comme suit :

Definition 16 Soit P est un VCSP et soit a et a sont deux valeurs dans ledomaine de la variable xi. a est dit directionnellement interchangeable etenduea a selon une orientation donnee du graphe de contraintes, (notationa =P a

), ssi a,a| j i b Dj,

a =Pji a (a, b) = (a, b) + a,a (3.7)

Pour simplifier, = va etre utiliser a la place de=P si ceci ne cause pas dam-

biguites. La relation = definie les domaines des valeurs interchangeablesetendues de chaque variable.

Un cas, interessant, est celui dans lequel chaque domaine de valeurs du pro-bleme est reduit a une chane de valeurs EDI. Les problemes dans cette classepeuvent etre resolus dans un temps polynomial.

Propriete 3 SoitP est un VCSP arc-consistant et est une orientation deson graphe de contraintes. Si chaque domaine de valeurs de P est une chainede valeurs EDI selon alors P peut etre resolu en un temps polynomial.

Preuve 3 Premierement, a a tel que a =Pji a,nous projetons la difference

a,a comme un cout unaire de la valeur a, comme suit :

Deuxiement, nous appliquons lalgorithme darc-consistance a P. Dans cestade, nous pouvons distinguer deux cas :


**********************************************************************61

8/7/2019 ch3et4

23/53


AlgorithmProject Costfor tout b Dj do

for tout a a Di doif a =Pji a

(a, b) = (a, b) + a,a then(a, b) = (a, b)(a) = a,a

un des domaines de valeurs de ac(P) est vides et donc P est inconsis-tant, par consequent nous navons aucune solution dans P permettantde satisfaire les contraintes dures.

tous les domaines de valeurs de ac(P) ne sont pas vides et donc ac(P) estarc-consistant. Alors nous devons choisir, entre les n-uplets de ac(D1). . . ac(Dn), un n-uplet t dont les composantes sont definies commesuit :

ti = arg minaiac(Di)

ci,jC, ij

(ai, aj) + (ai) (3.8)

Notons que aj est une valeur quelconque de ac(Dj). Cependent, aj peutetre une valeur quelconque de ac(Dj) car, etant donne que toutes les va-leurs de ac(Dj) sont EDI et que i j, toutes (ai, b)+(ai), b ac(Dj)sont equivalents.

Nous prouvons maintenant que t satisfait les contraintes dures, i.e. :

ci,jC, ij(ti , t

j ) <

Pour ce faire, nous supposons que

ci,jC, ij(ti , t

j ) =

Comme + est strictement monotone, ce ci veut dire quil existe ci,j C, i j tel que (ti, t

j) = . Nous nous pouvons pas avoir i

j si-non, (ti, t

j) = impliquera que (t

i, b) = pour toutes b ac(Dj)

car ac(Dj) est un sous ensemble de valeurs EDI selon . ti ne doit

pas avoir un support dans ac(Dj), ce qui contredit le fait que ac(P)est arc-consistant. Aussi nous nous pouvons pas avoir j i, sinon


**********************************************************************62

8/7/2019 ch3et4

24/53


(ti, tj) = impliquera que (a, t

j) = pour toutes a ac(Di) car

ac(Di

) est un sous ensemble de valeurs EDI selon . tj ne doit pas

avoir de support dans ac(Di), ce qui contredit le fait que ac(P) est arc-consistant. Et donc, nous avons une contradiction avec le fait que estun ordre totale. Alors, t satisfait les contraintes dures.

Dans cette etape nous prouvons que t est optimal. Par le choix de t

(en se referant a lequation 3.8), pour tout n-uplet t, nous avons,

i, 1 i n, (3.9)

ci,jC, ij(ti , t

j ) + (t

i ) (3.10)

ci,jC, ij(ti, t

j ) + (ti) (3.11)

Pourtant, chaque ac(Dj) est un sous-ensemble de valeurs de EDI selon, alors (ti, tj ) + (ti) = (ti, b) + (ti) pour toutes j, i j et pourtoutes b ac(Dj) et particulierement pour tj ac(Dj). Comme,

i, 1 i n,

ci,jC, ij(ti, t

j ) + (ti)

=

ci,j

C, ij(ti, tj) + (ti)

En se referant a (3.9), nous avons

i, 1 i n,

ci,jC, ij(ti , t

j ) + (t

i )

ci,jC, ij(ti, tj) + (ti)

Combinant avec loperateur monotone +, toutes les n inequations de(3.12), nous obtenons


**********************************************************************63

8/7/2019 ch3et4

25/53


ci,jC, ij

(ti , tj ) + (ti ) (3.12)

ci,jC, ij(ti, tj) + (ti) (3.13)

Et comme + est commutatif et associatif, (3.12) est vraie quelque soitlordre, particulierement lordre naturel.

ci,jC, i

8/7/2019 ch3et4

26/53


a =Pji a (a, b) = (a, b) + a,a

pour lordre j i.Et par suite a et a sont EDI dans P.

La consequence de la proposition 4 est que

Propriete 5 Pour nimporte quelle paire de problemes P = (X,D,C,S) et

P = (X, D, C , S ) tel que P P, si Di est une chaine de valeurs EDI dansP alors Di est une chaine de valeurs EDI dans P.

Preuve 5 La preuve resulte immediatement de la proposition 4 en observantque en une chaine, toutes les valeurs sont comparables.

3.4.2 Exploitation de lInterchangeabilite Directionnelle Etendue

La notion dinterchangeabilite directionnelle etendue peut etre utilisee pour

ameliorer la resolution de VCSPs binaires et ceci en lintegrant a lalgorithmedu Branch-and-Bound pour obtenir lalgorithme BABEDI (voir fonction 5).

Pour avoir une methode de resolution plus efficace, BABEDI integre ega-lement une procedure qui permet de maintenir larc-consistance durant larecherche comme dans lalgorithme de resolution de CSP MAC [29].

BABEDI prend comme parametres le VCSP a contraintes binaires a re-

soudre (X,D,C,S), (qui est suppose etre arc-consistant), une orientation dugraphe dinconsistance du probleme , lensemble des variables non encoreinstanciees Y et la meilleure solution courante I et procede comme suit :Il selectionne une variable non encore instanciee, calcule la partition de sondomaine de valeurs en des chaines de valeurs EDI : Di = {Di,1, . . . , Di,k} deDi est base en EDI. La partition EDI peut etre accomplie en O(nd

2) etapesen utilisant lalgorithme presente en [?] ou celui propose en [?].

lalgorithme itere sur les sous ensembles de la partion de domaine Di et reduita chaque iteration Di a Di,s Di, (voir ligne 7). Alors, la procedure Propagate


**********************************************************************65

8/7/2019 ch3et4

27/53


est appelee pour etablir larc-consistance local.

A ce stade, xi est consideree comme une variable instanciee, elle sera alorssupprimee de lensemble des variables non encore instanciees meme si sondomaine nest pas reduit a un singleton. Si aucun domaine vide nest ren-contre, donc lalgorithme execute un appel recursif pour traiter les variablesfutures. Sinon, il considere un autre element de Di. Si toutes les iterationsne rendent aucune solution, lalgorithm backtracks a la variable immediate-ment precedente. Au contraire, si BAB-EDI succede a instancier toutes lesvariables alors nous obtenons un paquet de solutions.

Algorithm BABEDI(Y, (X,D,C,S), , I);if Y = then

return(D);

elsexi Select(Y);Di DIPartition(Di, , (X,D,C));for Di,s Di do

Di Di,s;

Propagate(xi, Y {xi}, (X,D,C));if no empty domain then

I FCDI(Y {xi}, (X,D,C), );if I = then

return(I);

Restore (D);

return();

La procedure Propagate qui est decrite ci-dessous assure larc-consistancede chaque arc dont le sommet cible represente une variable instanciee. Soit xiest la variable courante. Propagate procede en deux etapes. Dans la premiereetape, tous les arcs (xj, xi) sont arc-consistant. Ensuite, Propagate traite toutles arcs (xk, xj) tel que xk est une variable non-instanciee et xj est une va-riable instanciee dont le domaine a ete modifie dans la premiere etape. Ilsensuit que pendant la deuxieme etape, le domaine de xi nest pas reduit de-sormais parceque xi est consideree dorenavant comme une variable instanciee.

Alors, tous les (xj, xi) restent arc-consistant. Propagate appelle ReviseDomain


**********************************************************************66

8/7/2019 ch3et4

28/53


qui est une fonction standard pour restaurer larc-consistance. La FonctionReviseDomain retourne vrai ssi elle a enleve quelques valeurs incoherentes.

Algorithm Propagate(xi, Y, (X , D, C ));Q ;for (xj, xi) do

if ReviseDomain((xj, xi), (X,D,C)) thenQ Q {(xk, xj) | xk Y and xj X Y};

for (xk, xj) Q doReviseDomain((xk, xj), (X,D,C));

3.5 Orientation du graphe dinconsistance

Lorientation du graphe dinconsistance utilisee comme reference (voir equa-tion 3.2) pour determiner les valeurs DS a un grand impact sur loccurrencedes valeurs DS. Les meilleures resultats ont ete obtenus lorsquon sait re-fere a une orientation qui favorise loccurrence des valeurs DS a des niveauxproches de la racine de larbre de recherche. Une telle orientation est obtenuedynamiquement en utilisant un algorithme glouton (voir fonction 7).

Au depart du processus de recherche, lorientation est vide. A chaque etape,lalgorithme dorientation ne considere que les aretes qui relient les valeurs dela variable courante a ceux des variables deja instanciees. Soit a une valeurquelconque de la variable courante qui est incompatible avec une valeur bdune variable deja instanciee. Larete {a, b} donnera lieu a larc (a, b), quisera ajoute a .

Cette strategie favorise loccurrence des valeurs DS a des niveaux prochesde la racine. En effet, rappelons que seulement les arcs sortants dune valeursont pris en consideration lors du calcul des conflits directionnels de cettevaleur. En ne considerant que les aretes qui vont vers les valeurs des variablesinstanciees, on augmente les chances des valeurs des variables traitees a desniveaux proches de la racine a etre DS les une aux autres. La raison de ceciest que, proche de la racine, il y a peu de variables instanciees.


**********************************************************************67

8/7/2019 ch3et4

29/53


Le fait de considerer de larges chaines de valeurs DS a des niveaux peu pro-fonds de larbre de recherche est une strategie souvent avantageuse car, a cestade, lheuristique dordre des valeurs ne dispose pas dassez dinformationspour faire des choix corrects de valeurs. En prenant des decisions portant surplusieurs valeurs, on peut eviter des erreurs qui, plus elles sont commises tot,plus elles sont couteuses en temps dexploration.

Algorithm Orientation(xi, , Y, (X,D,C,Z));for xj X Y | Ci,j C do

for a Di do

for b Dj | (a, b) / Rel(Ci,j) do {(a, b)};

Retourner();

3.6 Substituabilite directionnelle (DS) pour les VCSPs

Dans cette section, pour resoudre les VCSPs, nous allons exploiter la me-

thode de decomposition par la substituabilite directionnelle qui permet deresoudre les VCSPs binaires a contraintes binaires fixes.

Pour resoudre un VCSP nous proposons de passer par son duale. Nous com-mencons par la definition du duale dun CSP.

Definition 17 Le probleme dual dun CSP est une reformulation de ce pro-bleme de satisfaction de contraintes exprimant chaque contrainte du problemeoriginal comme une variable. Les problemes duales contiennent seulement descontraintes binaires et sont donc solubles par des algorithmes faconnes pourde tels problemes.

Par analogie, nous pouvons definir le duale dun VCSP comme suit :

Definition 18 Le probleme dual dun VCSP est une reformulation de ce pro-bleme de satisfaction de contraintes valuees exprimant chaque contrainte du

probleme original comme une variable dont la contrainte unaire de cette va-riable correspond au cout de la contrainte dans le probleme original.


**********************************************************************68

8/7/2019 ch3et4

30/53


Les problemes duales des VCSPs contiennent seulement des contraintes bi-naires et sont donc solubles par des algorithmes faconnes pour de tels pro-blemes. Parmi ces algorithmes nous proposons notre methode de decomposi-tion par la substituabilite directionnelle.

Propriete 6 Les VCSPs, reformules par leurs duales, sont solubles par lamethode de decomposition par la substituabilite directionnelle

Preuve 6 Les problemes duales contiennent seulement des contraintes bi-

naires a couts fixes En effet, le duale dun VCSP est un VCSP binaire acontraintes binaires fixes.

3.7 Resultats experimentaux

Lalgorithme darc-consistance employe est AC-3 [23]. Lheuristique dordrede variables est min-domain/wdeg[2], celle de lordre des valeurs privilegie, ona simule deux heuristiques : Dabord, les valeurs qui ont le moins de conflits

[11] (le BAB sera note dans ce cas par MC).

Ensuite, les valeurs les plus faibles(le BAB sera note dans ce cas par MV). Lafonction i, qui est indispensable pour definir la substituabilite directionnelle,est deduite de de maniere analogue a celle specifiee par lequation (3.6).

Les criteres devaluation des performances sont la taille de larbre de rechercheexploree, le temps de calcul et la qualite de la meilleure solution trouvee. Lesdeux algorithmes ont ete implementes en C++ et executes sur un PC a 2

GHZ de frequence et une memoire vive de 4GB.

Les problemes test utilises sont ceux references par js-taillard-15 dispo-nibles sur [21]. Ce sont dix instances de job-shops comportant 15 jobs et 15machines, (donc 225 taches), generes selon le modele decrit dans [32]. Pources instances de job-shop, la discretisation du temps maximum impartie pourexecuter toutes les taches donne plus de mille valeurs. Pour obtenir des solu-tions en des temps dexecution raisonnables pour des VCSPs-FbC impliquant

de si large domaines de valeurs, on a elargi davantage les domaines de valeurspour obtenir des instances plus faciles. Ainsi, on a multiplie les tailles des


**********************************************************************69

8/7/2019 ch3et4

31/53


domaines originaux par un facteur de 105%, 104% puis 103% pour obtenirdes instances qui vont des plus faciles aux plus difficiles. De plus, on a faitrecours a une recherche par divergence limitee [12], pour les deux algorithmes.

Les resultats obtenus (voir figures 3.10 et ??) montrent clairement que MC+DSet MV+DS ont trouve des solutions pour plus dinstances que MC ou MV.Pour les instances auxquelles les deux algorithmes ont reussit a trouver dessolutions, on constate que dans la plupart des cas, ou bien que la solution trou-vee par BABDS a un cout meilleur que celle trouvee par BAB, ou bien queBABDS trouve une solution ayant le meme cout mais en moins de temps.

Sur les trente instances considerees, il y a uniquement sis instances (MC-104-4, MC-104-7, MC-103-7, MV-105-6 et MV-104-9) sur lesquelles, BAB aete meilleur que BABDS. Enfin, la superiorite de BABDS ne semble pasdependre de la difficulte des instances, ni de lheuristique employee puisqueBABDS est globalement meilleur sur les deux niveaux de difficulte.


**********************************************************************70

8/7/2019 ch3et4

32/53


temps cout temps coutinstances MC MC+DS MC MC+DS MV MV+DS MV MV+DS

105-0 7065 651 1308 1308 225 1290105-1 90 3847 1326 1325 1573 1304105-2 11521 748 1295 1295 1173 1285105-3 3743 1239 6193 1234105-4 5503 1297 4491 12943 1291 1285105-5 2532 1308 2249 1309105-6 105 6056 1297 1296 2292 9559 1284 1286105-7 376 1282 523 1282105-8 3406 74 1353 1353 2541 1343105-9 3051 4681 1334 1333 739 13850 1334 1316

104-0 4526 1296 12157 3366 1292 1279104-1 460 1313 12147 1302104-2 88 1283 13812 1269104-3 646 2716 1228 1227 11080 1228104-4 1500 12942 1285 1285 10504 1281104-5 643 1297 104-6 1136 1284 766 1282104-7 2606 14028 1270 1270 104-8 61 539 1341 1340 4137 1340104-9 99 79 1321 1321 739 1318

103-0 122 1284 103-1 885 1301 3813 1284103-2 423 1271 389 1262103-3 9734 1213103-4 218 1270103-5 103-6 1274 1273

103-7 2513 1259 103-8 132 1327103-9 454 1309 8926 1287

Figure 3.10 Resultats obtenus par MC, MC+DS, MV et MV+DS sur les instances js-taillard-15-(105 a 103). Le temps CPU en secondes et le cout de la meilleure solution trou-vee sont raportes. Pour le temps CPU, on indique les temps auxquels ont ete trouvees lesmeilleures solutions. Le temps dexecution a ete limite a 4 heures par instance.


**********************************************************************71

8/7/2019 ch3et4

33/53


3.8 Conclusion

Dans ce chapitre, nous avons propose deux extensions a la notion de substi-tuabilite directionnelle presentee dans [24]. Tout dabord, nous avons gene-ralise davantage la substituabilite directionnelle en considerant, comme refe-rence, une orientation du graphe dinconsistance du probleme au lieu dunordre sur les variables du probleme. Puis, nous avons introduit des conditionssupplementaires de substituabilite garantissant loptimalite de la solution lorsde la resolution des problemes VCSPs.

Les resultats de simulation sur plusieurs VCSPsFbC qui codent des pro-blemes dordonnancement du type job-shop ont montre quune variante delalgorithme du Branch-and-Bound exploitant la substituabilite directionnelleest souvent plus efficace que lalgorithme original.

Une extension possible de ce travail consiste a proposer une formulation en-core plus generale que la substituabilite directionnelle afin de pouvoir lappli-quer aux VCSPs [30] en profitant de classes polynomiales plus importantes

lors de la decomposition.


**********************************************************************72

8/7/2019 ch3et4

34/53

Chapitre 4

Une methode de decompositionmodulaire pour les CSPs Valuees

Resume

De nombreux problemes combinatoires peuvent etre formules comme des Problemes de Sa-tisfaction de Contraintes Valuees (VCSPs) ou les contraintes sont definies a laide des fonctionsde valuation pour refleter les degres de coherence.

Pour resoudre un VCSP, il faut trouver une attribution de valeurs aux variables avec une valuationcomplete optimale. Particulierement pour plusieurs problemes, cette tache est difficile du point devue de la complexite.

Ce chapitre presente une methode de decomposition de domaine pour resoudre les VCSPs binaires.Elle sappuie sur la classe des fonctions modulaires [27]. Le processus de decomposition produitdes sous problemes dont les fonctions de valuation sont exclusivement modulaires.

Pour les VCSPs binaires avec de telles fonctions de valuation, nous proposons un algorithme

didentification de complexiteO(

ed2

) et un algorithme de resolution de complexiteO(

ed).

73

8/7/2019 ch3et4

35/53

Chapitre IV : Une methode de decomposition modulaire pour les CSPs Valuees

4.1 Introduction

La complexite algorithmique de la recherche de la solution optimale dunVCSP a ete etudiee dans plusieurs travaux de recherche. Et plusieurs classespolynomiales de VCSPs ont ete identifiees et resolues [7, 16, 6]. Les VCSPsimpliquant les fonctions de valuation binaires sous-modulaires est une desclasses polynomiales.

En effet, en exprimant ces VCSPs comme des problemes cherchant a trouverla coupe minimale dun graphe pondere, il est possible de les resoudre en

O(n3d3) etapes ou n est le nombre de variables et d est la taille du domainede valeur le plus large [5].

Neanmoins, les VCSPs resultant de cas reels ne sont pas limites a des fonc-tions sous-modulaires. Dans de tels cas, pouvons nous proceder de maniereplus efficace quune recherche exhaustive tout en reduisant la solution opti-male ? Y at-il moyen dexploiter les sous-modularite dans un contexte plusrestreint ?

Ce chapitre est destine pour contribuer a fournir des reponses positives a cesquestions. Motive par les resultats obtenus sur les CSPs [?], nous presentonsune methode de decomposition de domaine pour resoudre les VCSPs binaires.Elle sappuie sur la classe des fonctions modulaires [27]. Le processus de de-composition produit des sous problemes dont les fonctions de valuation sontexclusivement modulaires.

Pour les VCSPs binaires avec de telles fonctions de valuation, nous propo-sons un algorithme didentification de complexite O(ed2) et un algorithme deresolution de complexite O(ed).

Dans le present chapitre, nous proposons une methode modulaire de decom-position pour les VCSPs binaires. Les divers etapes de cette methode sontpresentees dans la figure 4.1.

Le chapitre est organise comme suit : la section suivante presente quelques

definitions et notations. La section 4.3 est consacree aux fonctions binaires


**********************************************************************74

8/7/2019 ch3et4

36/53


FbC1

2

nc

i

Figure 4.1 Les etapes de la Methode de decomposition modulaire de domaine pour lesVCSPs

modulaires et leur decomposition. Dans la section 4.4, nous presentons ladecomposition et des solutions algorithmiques pour les VCSPs binaires. Desresultats experimentaux sont annonces dans la section 4.5. Finalement, lasection 4.6 est une breve conclusion.

4.2 Definitions et Notations

Comme mentionne precedemment, nous sommes concernes par les algo-rithmes complets qui fonctionnent par recherche en profondeur (DFS) dansun arbre de recherche jusqua ce quune solution optimale soit trouvee ou ilest prouve quaucune solution nexiste.

A chaque noeud de larbre de recherche,les algorithmes de resolution de base,DFS, executent une reduction du probleme original. Cette reduction consiste


**********************************************************************75

8/7/2019 ch3et4

37/53


dans lassignation dune valeur a une variable et a enlever les valeurs qui sontdorenavant incoherentes avec la solution partielle ou ceux menant aux solu-tions sous-optimales.

Formellement, les problemes traites le long du meme chemin de larbre derecherche peuvent etre connectes par la relation suivante

Definition 19 Un probleme P = (X, D, C , S ) est dit etre une reduction deP = (X, D, C, S) (notation P P) si et seulement si

X = X ;

Di Di, pour chaque xi X; C1 = {ci | ci C

1 et i est la restriction de i a Di} ;

C2 = {ci,j | ci,j C

2 et i,j est la restriction de i,j a Di Dj} ;

S = S.

4.3 Les fonctions modulaires binaires

Dans cette section, nous definissons la fonction modulaire binaire, mettons

en evidence certaines de leur proprietes et montrons quelle peut etre exprimeecomme la somme de deux fonctions unaires.

4.3.1 Definitions et proprietes

Definition 20 Soit S = E, +, est une structure de valuation propre.Une fonction binaire f : D2 E sur lensemble fini D est modulaire enrespectant S si, pour tout u,x,v,y D, nous avons

f(u, v) + f(x, y) = f(u, y) + f(x, v) (4.1)

Soit on note M le sous-ensemble de toutes les fonctions modulaires de B etsoit f et fT sont deux fonctions binaires de B tel que pour tout u, v dansD, nous avons f(u, v) = fT(v, u). Alors, nous pouvons facilement deduire de(5.2) que f est dans M si et seulement si fT est dans M.

De (5.2), nous pouvons aussi deduire que, pour toute f dans M et tout v, y

dans D, la declaration suivante est vraie


**********************************************************************76

8/7/2019 ch3et4

38/53


u D, f(u, v) < f(u, y) u D, f(u, v) f(u, y) (4.2)

Notons M lensemble de toutes les fonctions modulaires binaires sur len-semble fini D avec lensemble totalement ordonne E comme le co-domaine.Soit fT est une fonction binaire deduite dune autre fonction binaire f commesuit

u, x D, fT(u, x) = f(x, u)

Il est facile de montrer que

f M fT M (4.3)

Soit u, x sont deux elements de D. De (5.2), nous deduisons ce qui suit

D, f(, u) f(, x) D, f(, u) f(, x) (4.4)

Cela signifie que la comparaison entre f(, u) et f(, x) ne depend pas de .

De plus, depuis est un ordre total sur E, il incite un ordre total sur leselements de D que nous denotons par et definissons comme suit

u x f(, u) f(, x), pour chaque D

Pour u,x, D tel que f(, u) f(, x) note par u,x la differencef(, u) f(, x). De (5.2), il est facile de montrer que u,x ne depend pas de :

u,x = f(, u) f(, x), D (4.5)

4.3.2 Reduction de fonctions modulaires binaires

Dans ce qui suit, nous montrons quune fonction modulaire binaire peutetre efficacement reduite a la somme de deux fonctions unaires.

Soit est un des elements minimaux de D selon .

= arg minuD

f(, u), pour chaque D (4.6)


**********************************************************************77

8/7/2019 ch3et4

39/53


et considerons les fonctions unaires f et f definis sur D avec des valuationsdans E comme :

f(u) = f(u, ) (4.7)

f(u) = f(, u) f(, ) (4.8)

ou est nimporte quel element de D. Notons que f(u) existe pour toutu D depuis par (4.6), nous avons f(, u) f(, ). De plus, selon (4.5),f(u) ne depend pas du choix de .

La propriete suivante rapproche a la fonction modulaire binaire f des fonc-tions unaires f et f.

Propriete 7 Soit f : D2 E est une fonction binaire. Alors f est modu-laire si et seulement si

f(u, v) = f(u) + f(v), u, v D (4.9)

Preuve 7 Nous prouvons dabord que la modularite assure (4.9). Par le fait

que f est modulaire, nous avons,

f(u, v) + f(, ) = f(u, ) + f(, v)

f(u, v) = f(u) + f(, v) f(, )

f(u, v) = f(u) + f(v)

Au contraire, pour tout u,v,x,y D, si (4.9) se tient alors

f(u, v) + f(x, y) = f(u) + f(v) + f(x) + f(y)= f(u) + f(y) + f(x) + f(v)

= f(u, y) + f(x, v)

Ci-dessous est le pseudo-code dun algorithme qui prend comme des para-metres de saisie une fonction modulaire binaire sur D et un element dansD et calcule les fonctions unaires f et f selon (4.7) et (4.8).

Exemple 16 Nous avons pris un exemple de fonction binaire modulaire f

(2 + 8 = 3 + 7), cette fonction est illustree par la Figure 4.2 (a).


**********************************************************************78

8/7/2019 ch3et4

40/53


Function Reduce(f , D, x) : f, fm arg minuD f(x, u)

for u D dof(u) f(u, m)

for u D dof(u) f(x, u) f(x, m)

Lalgorithme Reduce calcule m1 = min{3, 8} = 3 et m2 = min{2, 7} = 2.m1 et m2 seront stockees respectivement dans f(u) etf(x). (Voir Figure 4.2(b).)

Enfin, dans f(y) on stockera f(u, y) m1 = f(x, y) m2 = 5.

Comme la fonctionf est modulaire binaire, lapplication de lalgorithme Re-duce transforme toutes les fonctions binaires en des fonctions unaires f etf. (Voir Figure 4.2 (c)).

Propriete 8 Etant donne une fonction modulaire binaire f definie sur unensemble fini D avec lensemble totalement ordonne E comme co-domaine.Alors lalgorithme Reduce calcule deux fonctions unaires verifiant la pro-priete 7 dans O(|D|) etapes.

Preuve 8 Cette propriete peut etre facilement deduite du pseudo-code de lal-gorithme Reduce.

Propriete 9 Une fonction binaire f : D2 E peut etre identifiee commemodulaire dans O(|D|2) etapes.

Preuve 9 Selon la propriete 7, il suffit dappliquer lalgorithme Reduce quisexecute dans O(|D|) etapes et verifier ensuite des equations en |D|2 donnepar (4.9).

4.3.3 Decomposition en fonctions modulaires binaires

Dans ce paragraphe, nous montrons que, etant donne une fonction binairef qui nest pas necessairement modulaire, il est possible de diviser D en de

sous-ensembles pour quen limitant le premier argument de f a un de cessous-ensembles, nous obtenions une fonction binaire modulaire.


**********************************************************************79

8/7/2019 ch3et4

41/53


i

j

(u) (x)

(v) (y)

(u) (x)

(v) (y)

i

j

(u) (x)

(v) (y)

(u) (x)

(v) (y)

i

j

(u) (x)

(v) (y)

(u) (x)

(v) (y)

Figure 4.2 Illustration de lalgorithme Reduce

Definition 21 Soit f est une fonction binaire definie sur D avec E commele co-domaine et soit u, x sont deux elements de D. Nous disons que {u, x}est une paire modulaire par rapport a f (notation u f x) si et seulement sila restrection de f a {u, x} D est modulaire. Plus precisement, nous avons

u f x v, y D, f(u, v) + f(x, y) = f(u, y) + f(x, v) (4.10)

Notons que

f M u f x, u, x D (4.11)

Propriete 10 f est une relation dequivalence.

Preuve 10 La preuve est immediate de lequation (4.10).


**********************************************************************80

8/7/2019 ch3et4

42/53


Lalgorithme EquivClass, qui est decrit ci-dessous, prend une fonctionbinaire sur un ensemble fini D et un element dans D comme des argumentset calcule la classe dequivalence de , (denote par dans le pseudo-code),conformement a la definition 21.

Function EquivClass(f , D, x) : x(f, f) Decompose(f , D, x)x for u D do

equiv truefor v D do

if f(u, v) = f(u) + f(v) thenequiv falsebreak

if equiv thenx x {u}

Exemple 17 Cette fois, nous avons pris un exemple de fonction binaire nonmodulaire f (2 + 10 = 3 + 7), cette fonction est illustree par la Figure 4.3

(a).

Apres lapplication de lalgorithme Reduce (Figure 4.3 (b) et (c)). A la fin,(voir Figure 4.3 (c)) 10 = f(u, y) = f(u) + f(y) = 8.

Dou u / x, et donc u nappartient pas a la classe dequivalence de x on lenote par : u / [x].

Propriete 11 Pour une fonction binaire f defini sur un domaine fini D etun co-domaine totalement ordonne E, lalgorithme EquivClass calcule laclasse dequivalence de son argument selon la definition 21 dans O(|D|2)etapes.

Preuve 11 Nous pouvons voir du pseudo-code EquivClass quun elementu est insere dans si et seulement sif(u, v) = f(u)+f(v) pour toutv D.Dabord, nous verifions que lui meme est dans . Ceci est vrai depuis, pourtout v D, nous avons

f() + f(v) = f(, ) + f(, v) f(, ) = f(, v)


**********************************************************************81

8/7/2019 ch3et4

43/53


i

j

(u) (x)

(v) (y)

(u) (x)

(v) (y)

i

j

(u) (x)

(v) (y)

(u) (x)

(v) (y)

i

j

(u) (x)

(v) (y)

(u) (x)

(v) (y)

Figure 4.3 Illustration de lalgorithme EquivClass

Maintenant, nous prouvons que si u f alors u .Depuis u f , alors, pour tout v D, nous avons

f(u, v) + f(, ) = f(u, ) + f(, v)

f(u, v) + f() = f(u) + f() + f(v)

f(u, v) = f(u) + f(v)

La derniere equation est equivalente a u .Ensuite, nous prouvons linverse. Depuis u, , alors, pour tout v D,

nous avons f(u, v) = f(u) + f(v) et f(, v) = f() + f(v). Par (4.7) et(4.8) et pour tout v, y D, nous obtenons ce qui suit

f(u, v) + f(, y) = f(u) + f(v) + f() + f(y)

= f(u) + f(y) + f(, v) f(, ) + f()= f(u) + f(y) + f(, v) f() + f()


**********************************************************************82

8/7/2019 ch3et4

44/53


= f(u, y) + f(, v) (4.12)

La derniere equation est equivalente a u f .Finalement, nous pouvons facilement voir du pseudo-code de lalgorithme

EquivClass que ce dernier sexecute en O(|D|2) etapes.

Propriete 12 Soit f est une fonction modulaire et soit D1, . . . , Dk denotela partition de D obtenue par f. Alors la restriction de f a Ds D estmodulaire pour s = 1, . . . , k.

Preuve 12 La propriete resulte immediatement de (4.10) et le fait que chaqueDs est une classe dequivalence de f.

4.4 Un schema de decomposition pour les VCSPs

Dans ce qui suit, nous allons noter par sCSP (L) la classe de VCSPs binaireimpliquant les fonctions de valuation dans L.

Propriete 13 Denotons par U lensemble de tous D E des fonctions

unaires. La complexite de temps de calcul de sCSP (U) est O(nd).

Preuve 13 Un algorithme qui resout des cas dans sCSP(U) procede en met-tant en application la consistance de noeud. Alors, sil ny a aucun domainevide, il retourne n-tuple t verifiant :

ti = arg minvDi

i(v), i : 1, . . . , n

Cela peut etre accompli dans O(nd) etapes. De plus, nous avons P(t) =xiX i(ti) qui est minimal puisque loperateur daccumulation + est mono-

tone.

Dans ce qui suit, nous decrivons une methode pour decomposer les ins-tances des VCSPs binaire en ensembles dinstances dans sCSP(U M).


**********************************************************************83

8/7/2019 ch3et4

45/53


4.4.1 VCSP avec fonctions modulaires binaires

Soit ci,j est une contrainte binaire soft dont la fonction de valuation i,jest dans M. Alors, selon la section precedente, i,j peut etre exprime commela conjonction de deux contraintes unaires softs denotees par cij et cij, dontles portees sont respectivement xi et xj et dont les fonctions de valuationverifient :

i,j = ij + ij (4.13)

Definition 22 SoitP = (X, D, C , S ) est une instance de VCSP de sCSP(U M). La reduction unaire de P en respectant un ordre total sur X est leVCSP P = (X, D, C, S) definie par :

X = X D = D C = {ci |

i = i +

ci,j C

ij +

cj,i Cji}

S = S

Notons que, par definition, chaque reduction unaire est dans sCSP(U).

Propriete 14 SoitP = (X,D,C,S) est une instance de sCSP(U M) alorsla reduction unaire de P peut etre calcule en O(|C||D|).

Preuve 14 Il suffit de substituer par deux contraintes unaires chacune descontraintes binaires de P comme suggere par la propriete 7. Cette tache peutetre faite dans O(|D|). Comme il y a |C| contraintes dans P, dou le resultat.

Propriete 15 Nimporte quel instance P de sCSP( U M) est equivalent a

sa reduction unaire.

Preuve 15 Nous prouvons que la valuation dune attributiont a un ensemblede variables V X est la meme par P et par sa reduction unaire P, qui est

P(t) = P(t) (4.14)

Selon la definition 22 et les equations (2.1) et (4.13), nous obtenons ce quisuit :


**********************************************************************84

8/7/2019 ch3et4

46/53


P(t) =

ciC,xiVi(t[xi]) +

ci,j C,xi,xjV

i,j(t[xi, xj])

=

ciC,xiVi(t[xi]) +

ci,j C,xi,xjV

ij(t[xi]) + ij(t[xj])

=

ciC,xiVi(t[xi]) +

ci,j C,xi,xjV

ij(t[xi]) +

ci,j C,xi,xjV

ij(t[xj])

=

ciC,xiVi(t[xi]) +

ci,j C,xi,xjV

ij(t[xi]) +

cj,i C,xi,xjV

ji(t[xi])

=

ciC,xiV

i(t[xi]) +

ci,j C,xjV

ij(t[xi]) +

cj,i C,xjV

ji(t[xi])

=

ciC,xiV

i(t[xi])

= P(t)

4.4.2 Decomposition de domaine

La strategie de decomposition est basee sur la definition suivante.

Definition 23 Soit P = (X,D,C,S) est un VCSP et un ordre total sur

X. {u, x} Di est une paire modulaire sur P selon , (notation ui

P x),

si et seulement si pour tout ci,j C, nous avons u i,j x.

Pour simplifier, nous omettrons lindice dei

P quand cela naffecte pas laclarte.

Propriete 16 Soit P est un VCSP et un ordre total sur ses variables.Si les les valeurs de chaque domaine de P sont des paires modulaires enrespectant alors P est dans sCSP(U M).

Preuve 16 Par (4.11), nous obtenons que tous les i,j tel que xj xisont modulaires. Dautre part, par (4.3), les j,i tel que xj xi sont mo-dulaires depuis les i,j tel que xj xi sont modulaires. Dou, nous pouvonsdeduire que toutes les fonctions de valuation de P sont modulaires et doncP sCSP(U M).

Propriete 17i

est une relation dequivalance sur Di.


**********************************************************************85

8/7/2019 ch3et4

47/53


Preuve 17 Premierement, notons que la relationi

est lintersection de i,j

tel que ci,j C. Dautre part, il est connu que lintersection de lensembledes relations dequivalance est une relation dequivalance. Dou le resultatrecherche.

Une propriete essentielle des paires modulaires est quelles sont preserveespar la reduction de probleme. De la, nous avons ce qui suit :

Propriete 18 Soit P et P sont deux VCSPs tel que P P, un ordretotal sur les variables et soit u, x Di alors nous avons

ui

P x ui

P x

Preuve 18 Une paire modulaire depend seulement de contraintes binaires.Le dernier nest pas modifie par la reduction. Ainsi, si lequation (4.10) tientpour une paire de valeurs dans P alors elle tient pour cette paire dans Paussi.

4.4.3 La solution algorithmique

Lalgorithme ModMac decrit ci-dessous est une variante de lagorithmeMAC de [18]. Il decompose progressivement le VCSP initial en des sous pro-blemes dans le vCSP(UM) : classe basee sur des paires de valeur modulaires.

Lordre des variables selon lequel les paires de valeurs sont modulaires est de-termine dynamiquement, cest a dire, il peut varier au cours de la recherche.Cet ordre est implicitement determine par la liste des variables non encoreinstanciees Y dont les elements viennent apres ceux de X Y dans lordre.

La fonction principale dans le processus de decomposition est ModEquiv-Class qui est appelee a chaque noeud de larbre de recherche.

Il retourne la classe dequivalence (Di,v) de la valeur selectionnee (xi, v) (voirligne 2 dans le pseudo-code). Il est base sur EquivClass (voir Section ??)qui est appelee pour chaque fonction devaluation i,j de P tel que xi est lavariable courante et xj est une variable passee, i.e., une variable dans X Y.

Le domaine de xi est donc reduit a Di,v (ligne 3).


**********************************************************************86

8/7/2019 ch3et4

48/53


Ensuite, le sous-probleme resultant est de nouveau transforme en vue dobte-nir progressivement un sous probleme dans la classe vCSP(U). Cette etape estachevee par la fonction ModDecompose (ligne 4). Ce dernier est egalementexecutee a chaque noeud de larbre de recherche. Il appelle Decompose pourchaque fonction devaluation binaire i,j tel que xi est la variable courante etxj est une variable passee. Le role de cette procedure est de remplacer i,jpar deux fonctions devaluations unaires.

Puis, larc-consistance star est retabli. Pour que lalgorithme puisse procedera une recherche plus profonde, le VCSP arc-consistant star ne doit pas conte-

nir un domaine vide.

Un appel recursif est donc effectue pour envisager les autres variables. Cetteappelle retourne le cout (c) de la meilleure solution obtenue en reduisant ledomaine de xi a Di,v. Ensuite, lalgorithme annule leffet de reduire Di to Di,vet rejette des elements de Di,v de Di. Il restaure a nouveau larc-coherancestar du sous-probleme resultant et verifie sil ny a pas de domaine vide. Sicest le cas, lalgorithme effectue un deuxieme appel recursif qui retourne le

cout de la meilleure solution du probleme recu en parametre.

Chaque fois que lalgorithme parvient a instancier toutes les variables, onobtient un VCSP dont les contraintes sont toutes unaires et softs, i.e., dansla classe vCSP(U). Le dernier appel de AC le long de cette voie de reussitefournit, par consequent, le cout de la solution actuelle en temps polynomial.Le cout de cette derniere est enregistre dans c au cours des futures appelsrecursifs (ligne 1).

4.5 Resultats experimentaux

Les problemes etudies dans notre experimentation sont les problemes Max-CSPs aleatoires binaires, avec la liaison radio dassignation de frequences(RLFAP) et les problemes de planification.

Nous comparons lalgorithmeModMac

avecMac

. Lalgorithme arc-consistancesoft employe pour ces deux algorithmes est AC [18]. Les limites superieures


**********************************************************************87

8/7/2019 ch3et4

49/53


Algorithm ModMac(P = (X, D, C , S ), Y , lb) : c

if Y = then1 c lb

elsexi Select(Y)v Select(Di)

2 Di,v ModEquivClass(P, Y , Di, v)3 Di Di,v4 ModDecompose(P, xi)

lb AC(P)if / D then

c ModMac(P, Y {xi}, lb)

Restore(D)Di Di Di,vlb AC(P)if / D then

c ModMac(P, Y , lb)

Restore(D)

initiales utilisees par les deux solveurs sont ceux donnees dans les differents

fichiers de reference benchmark files.

Lheuristique dordre de variables est min-domain/deg. Pour celle de lordrede valeurs, Les deux algorithmes choisient les valeurs aux moindre cout unaireprojete.

Le cout de cette derniere est automatiquement calcule par application deAC. Les criteres devaluation sont le nombre de noeuds developpes expan-

ded nodes, Le temps de calcul CPU time en secondes et le cout de lameilleure solution trouvee. Tous les algorithmes ont ete implementes en C++et executes sur un PC a 1.8 GHZ de frequence et une memoire vive de 3 Gb.

Max-CSPs aleatoires binaires : pour les Max-CSPs aleatoires binaires,nous avons experimente sur les instances decrites dans [?] et generees en fonc-tion du modele de quatre parametres bien connu [?]. Lobjectif est de trouverune affectation avec un nombre minimum de contraintes non satisfaites pourun CSP surcontraint.


**********************************************************************88

8/7/2019 ch3et4

50/53


Le probleme est facilement exprime comme un VCSP en utilisant, pour lescouts binaires, 0 pour les paires de valeurs compatibles et 1 pour les pairesincompatibles.

Nous avons experimente sur certains des cas disponibles dans [?]. Ces cas sontobtenus en considerant deux niveaux de densite de graphe de contraintes :clairsemee sparse (S) et dense (D) et deux niveaux de tightess contraintes :en vrac loose(L) et etanchetight (T). La combinaison de ces classes donne4 differentes Classes de VCSPs : SL, ST, DL, DT.

Nous considerons justement dix cas en provenance de ces quatre classes. Laplupart des cas sont plutot difficiles a resoudre (voir la figure 4.4). Ils ont encommun un domaine de valeur uniforme de taille dix. Le nombre de variables,ce qui est indique immediatement apres les initiales de la classe dans le nomde linstance, varie de 25 a 50.

La Figure 4.4 fournit les resultats obtenus par ModMac et Mac. Deuxheures de temps dexecution ont ete consacre a chaque instance. Nous avons

rapporte le nombre de noeuds developpes, le temps dexloration de larbre derecherche et le cout de la meilleure solution trouvee. Pour ces cas, non struc-turees, aucun des deux algorithmes ne surpasse systematiquement lautre.

Neanmoins, on remarque que ModMac est plus concurrentiel sur les contraintessparsely VCSPs impliquant des relations loose.

Probleme daffectation de lien radiofrequence (RLFAP) :

ce sont des cas provenant dun probleme du monde reel, a savoir le pro-bleme celar RLFAP [?] qui a la particularite detre peu contraint.

Nous avons precisement experimente sur dix cas de ceux disponibles dans [?],dont cinq sont extraites du probleme celar6 et notes celar6-sub0 a 4. Les cinqautres instances sont extraites du probleme celar7 et sont notees celar7-sub0a 4 (voir Figure 4.5). Chacune de ces instances comprend 16 variables et unetaille maximale de domaine de 44 valeurs.

En examinant la Figure 4.5, nous remarquons que lorsque les deux algo-


**********************************************************************89

8/7/2019 ch3et4

51/53


rithmes explorent toute larbre de recherche, ModMac est toujours plusrapide que Mac.

En outre, sur les autres instances, qui sont plus difficiles a resoudre, Mod-Mac a systematiquement trouve une solution qui est, au moins, aussi bonneque celle trouvee par Mac . Globalement, on peut dire que, contrairementaux instances aleatoires, ModMac surpasse Mac sur tous ces instancesstructurees.

Problemes de planification :

Nous considerons precisement le probleme de transport DriverLog. Ce pro-bleme implique un ensemble de pilotes pour conduire les camions et les mo-biles dun emplacement de depart vers une destination objectif dune maniereefficace.

Plus de details sur ce probleme se trouve dans [?]. Les dix cas sur lesquelsnous avons experimente sont moyennement modelises comme WCSP depuisenviron la moitie des contraintes possibles sont presentes. Chacun des cas im-

plique des centaines de variables et une taille maximale de domaine de onzevaleurs.

La Figure 4.6 montre que ModMac domine Mac sur toutes, sauf une desinstances (driverlog04bc).

4.6 Conclusion

Dans ce chapitre, nous avons presente un algorithme de decomposition dedomaine pour resoudre les problemes binaires de satisfaction de contraintesevalues (VCSP). Le processus de decomposition propose instancie les va-riables en reduisant leurs domaines respectifs a des sous-ensembles de valeursmodulaires au lieu de singletons.

Il produit, a chaque feuille de larbre de recherche, un sous probleme dont

les fonctions devaluation sont exclusivement modulaires. Ces sous-problemessont resolus en temps polynomial.


**********************************************************************90

8/7/2019 ch3et4

52/53


expanded nodes time (in sec.) costinstance Mac ModMac Mac ModMac Mac ModMac

SL50-10-10-60-1 6097 6369 7164 5 4SL50-10-10-60-2 6099 6726 8 5SL40-10-13-60-1 1059 762 1063 721 3 3SL40-10-13-60-2 2261 1837 2298 1675 3 3DL30-10-25-48-1 67 215 66 200 2 2DL30-10-25-48-2 915 181 864 155 2 2ST25-10-21-85-1 527 1206 317 698 19 19ST25-10-21-85-2 604 3852 356 2148 20 20

DT25-10-25-87-1 1871 12387 1222 28 29DT25-10-25-87-2 4332 9833 2714 6546 3

Documents

ch3et4