CitationSee all >15 ReferencesSee all >3 Figures
15.06Pontificia Universidad Católica de Valparaíso19.06?cole des Ponts ParisTechAbstractWe propose a new interval constraint propagation algorithm, called MOnotonic Hull Consistency (Mohc), that exploits monotonicity of functions. The propagation is standard, but the Mohc-Revise procedure, used to filter/contract the variable domains w.r.t. an individual constraint, uses monotonic versions of the classical HC4- Revise and BoxNarrow procedures. Mohc-Revise appears to be the first adaptive revise procedure ever proposed in constraint programming. Also, when a function is monotonic w.r.t. every variable, Mohc-Revise is proven to compute the optimal/ sharpest box enclosing all the solutions of the corresponding constraint (hull consistency). Very promising experimental results suggest that Mohc has the potential to become an alternative to the state-of-the-art HC4 and Box algorithms.Discover the world's research13+ million members100+ million publications700k+ research projectsFigures
Actes JFPC 2010Exploitation de la monotonie des fonctions dans lapropagation de contraintes sur intervallesIgnacio Araya1Gilles Trombettoni1Bertrand Neveu21COPRIN, INRIA Sophia Antipolis, Universit?e Nice Sophia2Imagine, LIGM, Universit?e Paris-Est, France {neveu,trombe}@sophia.inria.frR?esum?eNous proposons un nouvel algorithme de propaga-tion de contraintes sur intervalles, appel?e consistanced’enveloppe monotone (Mohc), qui exploite la mono-tonie des fonctions. La propagation est standard, maisla proc?edure de r?evision Mohc-Revise, utilis?ee pourcontracter le domaine d’une variable par rapport `a unecontrainte individuelle, utilise des versions monotonesdes proc?edures classiques HC4-Revise et BoxNarrow.Mohc-Revise semble ^etre la premi`ere proc?edure de r?evi-sion adaptative en programmation par contraintes (surintervalles). Quand une fonction est monotone en toutesses variables, nous montrons que Mohc-Revise calculela bo^?te englobante optimale de la contrainte correspon-dante (Hull-consistance). Des r?esultats exp?erimentauxtr`es prometteurs sugg`erent que Mohc a le potentiel dedevenir une alternative aux algorithmes classiques HC4et Box.AbstractWe propose a new interval constraint propagationalgorithm, called MOnotonic Hull Consistency (Mohc),that exploits monotonicity of functions. The propagationis standard, but the Mohc-Revise procedure, used tofilter/contract the variable domains w.r.t. an individualconstraint, uses monotonic versions of the classical HC4-Revise and BoxNarrow procedures.Mohc-Revise appears to be the first adaptive re-vise procedure ever proposed in constraint program-ming. Also, when a function is monotonic w.r.t. everyvariable, Mohc-Revise is proven to compute the opti-mal/sharpest box enclosing all the solutions of the cor-responding constraint (hull consistency). Very promisingexperimental results suggest that Mohc has the potentialto become an alternative to the state-of-the-art HC4 andBox algorithms.1 IntroductionLes r?esolveurs de contraintes sur intervalles traitentles syst`emes d’?equations et d’in?egalit?es sur les r?eels.Leur fiabilit?e et leur performance croissantes leur per-mettent de r?esoudre des syst`emes qui apparaissentdans divers domaines comme la robotique [12], les sys-t`emes dynamiques de commande robuste ou la locali-sation de robots autonomes [9].Deux principaux types d’algorithmes de contrac-tion permettent de r?eduire les domaines des variables.Les algorithmes de type Newton sur intervalles sontdes g?en?eralisations aux intervalles des m?ethodes stan-dard d’analyse num?erique [13]. Les algorithmes decontraction/filtrage provenant de la programmationpar contraintes sont aussi au coeur des r?esolveurssur intervalles. Les algorithmes de propagation decontraintes HC4 et Box [3, 15] sont tr`es souvent uti-lis?es dans les strat?egies de r?esolution. Ils r?ealisent uneboucle de propagation et r?eduisent les domaines desvariables (c-`a-d am?eliorent leurs bornes) avec des pro-c?edures de r?evision sp?ecifiques (appel?ees HC4-Reviseet BoxNarrow) qui traitent les contraintes individuel-lement.HC4-Revise calcule la bo^?te optimale englobanttoutes les solutions d’une contrainte cquand la fonc-tion correspondante est continue et que chaque va-riable appara^?t une seule fois dans c. Si une variableappara^?t plusieurs fois dans c,HC4-Revise n’est g?en?e-ralement pas optimal. Dans ce cas, BoxNarrow calculeune enveloppe plus ?etroite. Le nouvel algorithme pr?e-sent?e dans cet article, appel?e Mohc-Revise, essaie detraiter le cas g?en?eral o`u plusieurs variables ont des oc-currences multiples dans c.Quand une fonction est monotone par rapport `a unevariable xdans une bo^?te, il est bien connu que l’ex-
tension aux intervalles de fbas?ee sur la monotoniene produit pas de surestimation due aux occurrencesmultiples de x.Mohc-Revise exploite cette propri?et?epour am?eliorer la contraction. La monotonie n’est g?e-n?eralement vraie que pour quelques paires (f , x) aud?ebut de la recherche, mais peut ^etre d?etect?ee pourplus de paires quand on traite des bo^?tes plus petitesen descendant dans l’arbre de recherche.Apr`es quelques rappels sur les CSP num?eriques,nous pr?esentons l’algorithme Mohc-Revise et ?etablis-sons quelques conditions qui en augmentent l’efficacit?e.Nous montrons que, si une fonction est monotone entoutes ses variables, Mohc-Revise calcule alors la bo^?teoptimale englobant toutes les solutions de la contrainte(propri?et?e de Hull-consistance). Des exp?erimentationssoulignent les performances de Mohc.2 Intervalles et CSP num?eriquesLes intervalles permettent des calculs fiables en g?e-rant les arrondis des calculs sur les nombres en virguleflottante.D?efinition 1 (D?efinitions de base, notations)Un intervalle [v] = [a, b]est l’ensemble {x∈R, a ≤x≤b}.IR est l’ensemble de tous les intervalles.v=a(resp. v=b) est le nombre `a virgule flottantequi est la borne gauche (resp. la borne droite) de[v].Mid([v]) est le milieu de [v].Diam([v]) := v-vest le diam`etre, ou taille, de [v].Une bo^?te [V] = [v1], ..., [vn]repr?esente le produit car-t?esien [v1]×... ×[vn].L’arithm?etique d’intervalles a ?et?e d?efinie pour?etendre `a IR les fonctions ?el?ementaires sur R[13].Par exemple, la somme sur intervalles est d?efinie par[v1]+[v2] = [v1+v2, v1+v2]. Quand une fonction festla composition de fonctions ?el?ementaires, une exten-sion de faux intervalles doit ^etre d?efinie pour assurerun calcul d’image conservatif.D?efinition 2 (Extension d’une fonction `a IR)Soit une fonction f:Rn→R.[f] : IRn→IR est une extension de faux intervallessi :?[V]∈IRn[f]([V]) ? {f(V), V ∈[V]}?V∈Rnf(V) = [f](V)L’ extension naturelle [f]Nd’une fonction r?eellefcorrespond `a l’utilisation directe de l’arithm?etiqued’intervalles. L’extension par monotonie est particuli`e-rement utile quand une fonction fest monotone parrapport `a une variable vdans une bo^?te donn?ee [V],ce qui est le cas si l’?evaluation de la d?eriv?ee partiellede fpar rapport `a vest positive (ou n?egative) en toutpoint de [V]. Par abus de langage, nous dirons parfoisque vest monotone.D?efinition 3 (fmin,fmax , extension par monotonie)Soit fune fonction d?efinie sur les variables Vde do-maines [V]. Soit X?Vun sous-ensemble de variablesmonotones.Consid?erons les valeurs x+iet x-itelles que : sixi∈Xest une variable croissante (resp. d?ecrois-sante), alors x-i=xiet x+i=xi(resp. x-i=xiet x+i=xi).Soit W=V\Xl’ensemble des variables non d?etec-t?ees monotones. Alors, fmin et fmax sont les fonctionsd?efinies par :fmin(W) = f(x-1, ..., x-n, W )fmax(W) = f(x+1, ..., x+n, W )Finalement, l’extension par monotonie [f]Mde fdans la bo^?te [V]produit l’intervalle image suivant :[f]M([V]) = h[fmin]N([W]),[fmax ]N([W])iLa monotonie des fonctions est g?en?eralement utilis?eecomme un test d’existence calculant si 0 appartient`a l’intervalle image d’une fonction. Elle a aussi ?et?e uti-lis?ee dans les CSP num?eriques quantifi?es pour contrac-ter facilement une variable quantifi?ee universellementqui est monotone [8].Consid?erons par exemple :f(x1, x2, w) = -x21+x1x2+x2w-3wdans la bo^?te[V] = [6,8] ×[2,4] ×[7,15].[f]N([x1],[x2],[w]) = -[6,8]2+[6,8] ×[2,4] +[2,4] ×[7,15] -3×[7,15] = [-83,35].?f?x1(x1, x2) = -2x1+x2, et [ ?f?x1]N([6,8],[2,4]) =[-14,-8]. Comme [-14,-8] &0, nous en d?eduisonsque fest d?ecroissante par rapport `a x1. Avec le m^emeraisonnement, nous d?eduisons que x2est croissante.Finalement, 0 ∈[?f?w ]N([x1],[x2],[w]) = [-1,1], ainsiwn’est pas d?etect?ee monotone. Suivant la d?efinition 3,l’?evaluation par monotonie donne :[f]M([V]) = h[f](x1, x2,[w]),[f](x1, x2,[w])i=h[f](8,2,[7,15]),[f](6,4,[7,15])i= [-79,27]2.1 Le probl`eme de d?ependance (occurrences mul-tiples)Le probl`eme de d?ependance est le point d’achoppe-ment de l’arithm?etique d’intervalles. Il est d^u au faitque les occurrences multiples d’une m^eme variable dansune expression sont trait?ees comme des variables dif-f?erentes par l’arithm?etique d’intervalles. Dans notre
exemple, il explique pourquoi l’intervalle image calcul?epar [f]Mest diff?erent et plus ?etroit que celui produitpar [f]N. De plus, si on utilisait une forme factoris?eecomme -x21+x1x2+ (x2-3)w, on obtiendrait uneimage encore meilleure. Le probl`eme de d?ependancerend en fait NP-difficile le probl`eme de trouver l’inter-valle image optimal d’un polyn^ome [10]. (L’extensioncorrespondante est not?ee [f]opt .) Le fait que l’exten-sion par monotonie remplace les intervalles par leursbornes explique la proposition suivante.Proposition 1 Soit fune fonction continue sur [V].Alors,[f]opt([V]) ?[f]M([V]) ?[f]N([V])De plus, si fest monotone dans la bo^?te [V]parrapport `a toutes ses variables apparaissant plusieursfois dans f, alors l’extension par monotonie calculel’image optimale :[f]M([V]) = [f]opt([V])2.2 CSP num?eriquesL’algorithme Mohc pr?esent?e dans cet article contri-bue `a la r?esolution de syst`emes de contraintes non li-n?eaires ou CSP num?eriques.D?efinition 4 (NCSP)Un CSP num?erique P= (V, C, [V]) comprend unensemble de contraintes C, un ensemble Vde nva-riables ayant pour domaines [V]∈IRn.Une solution S∈[V]de Psatisfait toutes lescontraintes de C.Pour trouver toutes les solutions d’un NCSP avecdes techniques par intervalles, le processus de r?eso-lution commence avec une bo^?te initiale repr?esentantl’espace de recherche et construit un arbre de re-cherche, suivant un sch?ema Brancher & Contracter.–Brancher : la bo^?te courante est bissect?ee surune dimension (variable) et produit deux sous-bo^?tes.–Contracter : les algorithmes de filtrage (aussi ap-pel?es de contraction) r?eduisent les bornes de labo^?te sans perdre de solution.Le processus se termine avec des bo^?tes atomiquesde taille au plus ωsur chaque dimension.Les algorithmes de contraction comprennent les al-gorithmes de type Newton sur intervalles issus de lacommunaut?e num?erique d’analyse par intervalles [13]ainsi que des algorithmes venant de la programma-tion par contraintes. L’algorithme de contraction pr?e-sent?e dans cet article prend en compte la monoto-nie des fonctions, en adaptant les proc?edures clas-siques HC4-Revise et BoxNarrow de programmationpar contraintes sur intervalles. L’algorithme HC4 ef-fectue une boucle de propagation de type AC3. Saproc?edure de r?evision, appel?ee HC4-Revise, traversedeux fois l’arbre repr?esentant l’expression math?ema-tique de la contrainte pour contracter les intervallesdes variables de la contrainte. Un exemple est donn?e`a la figure 1.Box est un autre algorithme de propagation. Pourchaque paire (f, x), o`u fest une fonction du NCSPconsid?er?e et xest une variable de f,BoxNarrow rem-place d’abord les aautres variables de fpar leursintervalles [y1], ..., [ya]. Ensuite, la proc?edure r?eduitles bornes de [x] de telle sorte que la nouvelle bornegauche (resp. droite) soit la solution la plus `a gauche(resp. `a droite) de l’?equation f(x, [y1], ..., [ya]) = 0. Lesproc?edures existantes utilisent un principe de rognagequi ?elimine de [x] les sous-intervalles [xi] aux bornesde [x] qui ne satisfont pas la contrainte.Contracter de mani`ere optimale une bo^?te par rap-port `a une contrainte individuelle revient `a atteindre lapropri?et?e que l’on appelle hull-consistance. Commepour le calcul de l’intervalle image optimal, la hull-consistance n’est pas atteignable en temps polynomial,`a cause du probl`eme de la d?ependance. HC4-Revisecalcule la hull-consistance des contraintes sans variableavec occurrences multiples, `a condition que la fonc-tion et ses fonctions de projection soient continues. LaBox-consistance obtenue par l’algorithme BoxNarrowest plus forte [7] et produit la hull-consistance quandla contrainte ne contient qu’une variable avec occur-rences multiples. En effet, le processus de rognage r?ea-lis?e par BoxNarrow sur une variable xlimite fortementl’effet de surestimation sur x. Par contre, il n’est pasoptimal dans le cas o`u d’autres variables yiposs`edentaussi des occurrences multiples.Ces algorithmes sont parfois utilis?es dans nosexp?erimentations comme des sous-contracteurs de3BCID [14], une variante de 3B [11]. 3B utilise un prin-cipe de r?efutation par rognage. Un sous-intervalle [xi]`a une borne d’un intervalle [x] est supprim?e si l’ap-pel au sous-contracteur (par exemple HC4) sur le sous-probl`eme correspondant (o`u [x] est remplac?e par [xi])aboutit `a un ?echec (sous-probl`eme sans solution). Onproc`ede ainsi de chaque c^ot?e jusqu’`a ce qu’on obtienneune tranche ne pouvant pas ^etre supprim?ee ou quetoutes les tranches l’aient ?et?e.3 L’algorithme MohcL’algorithme de consistance d’enveloppe monotone(MOnotonic Hull-Consistency,Mohc) est un nouvel al-gorithme de propagation de contraintes qui exploite lamonotonie des fonctions pour mieux contracter unebo^?te. La boucle de propagation est exactement le
m^eme algorithme de type AC3 mis en oeuvre par HC4et Box. Sa nouveaut?e r?eside dans la proc?edure Mohc-Revise traitant une contrainte f(V) = 0 individuelle-ment1et d?ecrite `a l’algorithme 1.Algorithm 1 Mohc-Revise (in-out [V] ; in f,V,ρmohc,τmohc ,?)HC4-Revise (f(V) = 0,[V])if MultipleOccurrences(V)and ρmohc[f]& τmohcthen(X, Y, W, fmax , fmin,[G]) ←PreProcessing(f , V, [V])MinMaxRevise ([V], fmax, fmin , Y, W )MonotonicBoxNarrow ([V], fmax, fmin , X, [G], ?)end ifMohc-Revise commence par appeler la proc?edurebien connue et peu co^uteuse HC4-Revise. Les proc?e-dures de contraction par monotonie (MinMaxReviseet MonotonicBoxNarrow) ne sont appel?ees que si Vcontient au moins une variable apparaissant plusieursfois (fonction MultipleOccurrences). L’autre condi-tion rend Mohc-Revise adaptatif. Cette condition d?e-pend d’un param`etre utilisateur τmohc d?etaill?e dansla partie suivante. Le second param`etre ?de Mohc-Revise est un ratio de pr?ecision utilis?e par Monoto-nicBoxNarrow.La proc?edure PreProcessing calcule le gradient def. Le gradient est stock?e dans le vecteur [G] et utilis?epour r?epartir les variables de Ven trois sous-ensemblesX,Yet W:– les variables de Xsont monotones et ont des oc-currences multiples dans f,– les variables de Yn’ont qu’une seule occurrencedans f(elles peuvent ^etre monotones),– les variables wde Wapparaissent plusieurs foisdans fet ne sont pas d?etect?ees monotones, c.-`a-d. 0 ∈[? f?w ]N([V]).La proc?edure PreProcessing d?etermine aussi lesdeux fonctions fmin et fmax, introduites dans la d?efi-nition 3, qui approximent fen utilisant sa monotonie.Les deux proc?edures suivantes sont au coeur deMohc-Revise et sont d?etaill?ees plus loin. Utilisant lesmonotonies de fmin et fmax,MinMaxRevise contracte[Y] et [W] tandis que MonotonicBoxNarrow contracte[X].HC4-Revise,MinMaxRevise et Monotonic-BoxNarrow calculent quelquefois une bo^?te vide[V], prouvant alors l’absence de solution. Uneexception terminant la proc?edure est alors lev?ee.A la fin, si Mohc-Revise a contract?e un intervallede [W] (de plus qu’un ratio donn?e par le param`etreutilisateur τpropag ), alors la contrainte est mise dans la1La proc?edure peut facilement ^etre ?etendue pour traiter unein?egalit?e.queue de propagation pour ^etre trait?ee de nouveau parun appel suivant `a Mohc-Revise. Sinon, nous savonsqu’un point fixe en terme de filtrage a ?et?e atteint (voirlemmes 2 et 4).3.1 La proc?edure MinMaxReviseNous savons que :(?X∈[X])(?Y∈[Y])(?W∈[W]) : f(X∪Y∪W) = 0==>fmin(Y∪W)≤0et 0≤fmax (Y∪W)La contraction apport?ee par MinMaxRevise est sim-plement obtenue en appelant HC4-Revise sur lescontraintes fmin(Y∪W)≤0 et 0 ≤fmax(Y∪W)pour r?eduire les intervalles des variables de Yet W(voir l’algorithme 2).Algorithm 2 MinMaxRevise (in-out [V] ; in fmax,fmin,Y,W)HC4-Revise(fmin(Y∪W)≤0,[V]) /* MinRevise */HC4-Revise(fmax(Y∪W)≥0,[V]) /* MaxRevise */La figure 1 illustre comment MinMaxRevisecontracte la bo^?te [x]×[y] = [4,10] ×[-80,14] parrapport `a la contrainte : f(x, y) = x2-3x+y= 0.^2x-34y+0≤4[-80,-4][-76,0][16,16][-76,18][-80,14][12,12][-76,0][4,4]HC4-Revise(fmin(y)≤0)^2x-310y+0≥10[-70,-4][0,66][100,100][-10,66][-80,-4][30,30][0,66][70,70]HC4-Revise(fmax(y)≥0)nplusnminusnplusnminusFig. 1 – MinRevise (`a gauche) et MaxRevise (`a droite)appliqu?ees `a x2-3x+y= 0.La figure 1-gauche montre la premi`ere ?etape de Min-MaxRevise. L’arbre repr?esente l’in?egalit?e f(4, y) =fmin(y)≤0. HC4-Revise proc`ede en deux phases. Laphase d’?evaluation ?evalue chaque noeud de bas en hautavec l’arithm?etique d’intervalles et attache le r?esul-tat au noeud. La seconde phase, `a cause de l’in?egalit?e,commence par intersecter l’intervalle du haut [-76,18]avec [-∞,0] et, si le r?esultat est non vide, redescenddans l’arbre en appliquant les fonctions de projection(“inverses”). Par exemple, comme nplus =nminus +y,la fonction inverse de cette somme est la diff?erence[y]←[y]∩([nplus]-[nminus ]) = [-80,14] ∩([-76,0] -[4,4]) = [-80,-4]. Suivant le m^eme principe, MaxRe-vise applique HC4-Revise `a f(10, y) = fmax(y)≥0et r?eduit [y] `a [-70,-4] (cf. la figure 1-droite).Notons qu’un appel direct `a HC4-Revise sur lacontrainte x2-3x+y= 0 (sans utiliser la mono-tonie de f) n’aurait apport?e aucune contraction `a [x]ni `a [y].
3.2 La proc?edure MonotonicBoxNarrowCette proc?edure effectue une boucle sur chaque va-riable monotone xide Xpour contracter [xi].`A chaque it?eration, elle travaille avec deux fonctionssur intervalles, dans lesquelles toutes les variables deX, sauf xi, ont ?et?e remplac?ees par une borne de l’in-tervalle correspondant :[fximin](xi) = [f]N(x-1, ..., x-i-i, xi, x-i+1, ..., x-n,[Y],[W])[fximax](xi) = [f]N(x+1, ..., x+i-i, xi, x+i+1, ..., x+n,[Y],[W])Comme Yet Wont ?et?e remplac?ees par leurs do-maines, [fximax] et [fximin] sont des fonctions intervallesde la seule variable xi(cf. la figure 2).MonotonicBoxNarrow appelle deux sous-proc?edures :– Si xiest croissante, alors sont appel?ees :–LeftNarrowFmax sur [fximax] pour am?eliorer xi,–RightNarrowFmin sur [fximin] pour am?eliorer xi.– Si xiest d?ecroissante, alors sont appel?es :–LeftNarrowFmin sur [fximin] pour am?eliorer xi,–RightNarrowFmax [fximax] pour am?eliorer xi.Nous d?etaillons dans l’algorithme 3 comment laborne gauche de [x] est am?elior?ee par la proc?edureLeftNarrowFmax qui utilise [fxmax].Algorithm 3 LeftNarrowFmax (in-out [x] ; in [fxmax],[g], ?)if [fxmax]N(x)&0 /* test d’existence */ thensize ←?×Diam([x])[l]←[x]while Diam([l]) & size doxm←Mid([l]) ; zm←[fxmax](xm)/* zm←[fxmin](xm)dans {Left|Right}NarrowFmin */[l]←[l]∩xm-zm[g]/* it?eration de Newton */end while[x]←?l, x?end ifLe processus est illustr?e par la fonction repr?esent?eegraphiquement `a la figure 2. Le but est de contracter[l] (initialis?e `a [x]) pour obtenir un encadrement ?etroitdu point L. L’utilisateur sp?ecifie le param`etre de pr?e-cision ?(comme un rapport de diam`etres d’intervalles)donnant la qualit?e de l’approximation. LeftNarrowF-max conserve seulement l`a la fin, comme le montrentla derni`ere ligne de l’algorithme 3 et l’?etape 4 `a la fi-gure 2.Un test d’existence pr?eliminaire v?erifie que[fxmax]N(x)&0, c.-`a-d. que le point Asur la figure 2est en dessous de z?ero. Sinon, [fxmax]N≥0 est satisfaiten xet [x] ne peut ^etre r?eduit, ce qui aboutit `ala terminaison de la proc?edure. Nous effectuons unprocessus dichotomique jusqu’`a ce que l’on obtienne[fmax]x[l0]=[x]xABC123L[x]←[l,x]4[l1][l2]Fig. 2 – It?erations de Newton sur intervalles pour r?e-duire x.Diam([l]) ≤size. Des it?erations de l’algorithmeclassique Newton sur intervalles univari?e sont lanc?ees`a partir du point milieu xmde [l], comme sur lafigure 2 :1. `a partir du point B(milieu de [l0], c.-`a-d., [l] `al’?etape 0) et2. `a partir du point C(milieu de [l1]).Graphiquement, une it?eration de Newton sur inter-valles univari?e intersecte [l] avec la projection sur l’axexd’un c^one (deux demi-droites `a partir de B, puis deC). Les pentes de ces droites sont ?egales aux bornes dela d?eriv?ee partielle [g] = [ ? f xmax?x ]N([x]). Notons que lec^one forme un angle d’au plus 90 degr?es car la fonctionest monotone et [g] est positif. Ceci explique pourquoiDiam([l]) est divis?e au moins par 2 `a chaque it?eration.Lemme 1 Soit ?la pr?ecision exprim?ee comme unrapport de diam`etres d’intervalles. Alors, LeftNar-rowFmax et les proc?edures sym?etriques terminent ets’ex?ecutent en un temps en O(log(1?)).Observons que les it?erations de Newton appel?ees`a l’int?erieur de LeftNarrowFmax et RightNarrowFmaxtravaillent sur zm= [fxmax](xm), qui est une courbe(en gras sur la figure), et non la fonction sur inter-valles [fxmax](xm).3.3 Points notables de Mohc-ReviseComment rendre Mohc-Revise adaptatifLe param`etre utilisateur τmohc ∈[0,1] permet d’ap-peler plus ou moins souvent, au cours de la recherchearborescente, les proc?edures utilisant la monotonie(voir l’algorithme 1). Pour chaque contrainte, les pro-c?edures exploitant la monotonie de fne sont appel?eesque si ρmohc[f]& τmohc . Cette condition demande quel’image d’une fonction par l’?evaluation par monotonie
soit plus ?etroite que celle donn?ee par l’?evaluation natu-relle d’un facteur ρmohc[f] au moins ?egal au param`etreτmohc :ρmohc[f] = Diam([f]M([V]))Diam([f]N([V]))Comme nos exp?erimentations le confirment, ce ratioest pertinent pour les phases d’?evaluation de MinRe-vise et MaxRevise, et aussi pour MonotonicBoxNar-row qui effectue beaucoup d’?evaluations.ρmohc est calcul?e dans une proc?edure de pr?etraite-ment appel?ee apr`es chaque bissection. Comme de plusen plus de cas de monotonie apparaissent au fur et`a mesure que l’on descend dans l’arbre de recherche(les bo^?tes devenant plus petites), Mohc-Revise estcapable d’activer de mani`ere adaptative la machine-rie li?ee `a la monotonie. Mohc-Revise appara^?t ainsicomme la premi`ere proc?edure de r?evision adaptativeen programmation par contraintes (sur intervalles).Le regroupement d’occurrences pour utiliser plus demonotonieUn appel `a une nouvelle proc?edure appel?ee Regrou-pement d’occurrences a en fait ?et?e ajout?e `a Mohc-Revise juste apr`es le pr?etraitement. Si fn’est pasmonotone par rapport `a une variable x, il est toute-fois possible que fsoit monotone par rapport `a unsous-groupe des occurrences de x. Pour trouver detels sous-groupes d’occurrences croissantes et d?ecrois-santes, cette proc?edure utilise une approximation de fbas?ee sur l’?evaluation de Taylor et r?esout `a la vol?ee unprogramme lin?eaire. Ceci permet d’am?eliorer l’?evalua-tion par monotonie de f. Des d?etails et une ?evaluationexp?erimentale se trouvent dans [2].4 Propri?et?esProposition 2 (Complexit?e en temps)Consid?erons une contrainte ccomprenant nvariableset eop?erateurs unaires et binaires (n≤e). Soit ?lapr?ecision exprim?ee comme un ratio de diam`etres d’in-tervalles. Alors,la complexit?e en temps de Mohc-Revise est enO(n e log(1?)) = O(e2log(1?)).La complexit?e en temps est domin?ee parMonotonicBoxNarrow (voir le lemme 1). Un ap-pel `a HC4-Revise et un calcul du gradient sont tousdeux en O(e) [3].Proposition 3 Soit c:f(X) = 0 une contrainte telleque fest continue, d?erivable et monotone par rap-port `a chaque variable dans la bo^?te [X]. Alors, avecune pr?ecision ?,MonotonicBoxNarrow calcule la hull-consistance de c.On peut trouver les preuves dans [1] et [5]. Cepen-dant, la nouvelle proposition 4 ci-apr`es est plus fortecar les variables apparaissant une seule fois (Y) sonttrait?ees par MinMaxRevise et non par MonotonicBox-Narrow.Proposition 4 Soit c:f(X, Y ) = 0 une contrainte,o`u les variables dans Yapparaissent une seule foisdans f. Si fest continue, d?erivable et monotone parrapport `a chaque variable dans la bo^?te [X∪Y], alors,avec une pr?ecision ?,Mohc-Revise calcule la hull-consistance of c.On peut trouver la d?emonstration compl`ete dans [1].Il est aussi prouv?e qu’aucune hypoth`ese de monoto-nie n’est requise pour les variables de Y, `a conditionque Mohc-Revise utilise la variante combinatoire TAC-Revise [6] de HC4-Revise.Les lemmes 2, 3 et 4 ci-dessous permettent de d?e-montrer les propositions 3 et 4. Ils d?emontrent aussila correction de Mohc-Revise.Lemme 2 Quand MonotonicBoxNarrow r?eduit l’in-tervalle d’une variable xi∈Xen utilisant [fximax](resp. [fximin]), alors, pour tout j6=i,[fxjmin](resp.[fxjmax]) ne peut pas apporter de contraction addition-nelle `a l’intervalle [xj].Le lemme 2 est une g?en?eralisation de la proposition 1de [5] aux fonctions sur intervalles ([fximax] et [fximin]).Lemme 3 Si 0∈[z]=[fmax]([Y∪W]) (resp. 0∈[z] = [fmin]([Y∪W])), alors MonotonicBoxNarrow nepeut pas contracter un intervalle [xi](xi∈X) en uti-lisant [fximin](resp. [fximax]).Lemme 4 Si MonotonicBoxNarrow (suivant un appel`a MinMaxRevise) contracte [xi](avec xi∈X), alorsun second appel `a MinMaxRevise ne peut pas contrac-ter davantage [Y∪W].Les lemmes 2 et 4 expliquent pourquoi il n’est pasn?ecessaire d’effectuer de boucle dans MohcRevise pouratteindre un point fixe en termes de filtrage.4.1 D?emonstrations des lemmes 3 et 4La figure 3 illustre ces d?emonstrations dans le caso`u fest croissante. Nous distinguons deux cas suivantla borne droite initiale de l’intervalle [xi].Dans le lemme 3, nous avons 0 ∈[z]=[fmax ]([Y∪W]), c.-`a-d. z≤0≤z. Cette condition est en par-ticulier vraie quand MaxRevise apporte une contrac-tion. On peut v?erifier que xine peut ^etre am?elior?epar RightNarrowFmin : puisque xiest une solution de[fximax](xi) = 0 (le segment en gras sur la figure 3),
xi&xizzz&z&zzLxizR[fmin]xi[fmax]xixiLemma 3Lemma 4[xi][xi][xi&]Fig. 3 – D?emonstration des lemmes 3 et 4 montrant la dua-lit?e de MinMaxRevise et MonotonicBoxNarrow. [z] est l’image de[fmax] obtenue par la phase d’?evaluation de MaxRevise.xisatisfait aussi la contrainte [fximin](xi)≤0 qui estutilis?ee par RightNarrowFmin.Dans le lemme 4, nous avons 0 &[z]=[fmax ]([Y∪W]) (MaxRevise n’apporte pas de contraction). Apr`esla contraction r?ealis?ee par RightNarrowFmin, la bornedroite de l’intervalle devient x0i. Une nouvelle ?evalua-tion de [fmax]([Y∪W]) donne [z0] qui est encore audessus de 0, de telle sorte qu’un deuxi`eme appel `a Max-Revise n’apporterait pas de contraction additionnelle.24.2 Am?elioration de MonotonicBoxNarrowFinalement, les lemmes 2 et 3 apportent des condi-tions simples pour ?eviter des appels `a LeftNarrowFmax(et aux proc?edures sym?etriques) `a l’int?erieur de Mono-tonicBoxNarrow.Avec l’ajout de ces conditions, comme le montrentles tests d?etaill?es dans [1], 35% du temps CPU deMohc-Revise est pass?e dans MinMaxRevise alors queseulement 9% est pass?e dans la proc?edure plus co^u-teuse MonotonicBoxNarrow (entre 1% et 18% selonl’instance).5 Exp?erimentationsNous avons implant?e Mohc dans la biblioth`eque enC++ Ibex [4] de r?esolution par intervalles. Tous les algo-rithmes concurrents, HC4,Box,Octum [5], 3BCID(HC4),3BCID(Box) et 3BCID(Octum) sont aussi disponiblesdans Ibex, ce qui rend la comparaison ?equitable.Mohc et ses comp?etiteurs ont ?et?e test?es sur la m^ememachine Intel
GHz sur 17 NCSP avec unnombre fini de solutions ponctuelles disponibles surle site de COPRIN2. Nous avons s?electionn?e tous les2www-sop.inria.fr/coprin/logiciels/ALIAS/Benches/benches.htmlNCSP avec des variables `a occurrences multiples quise trouvent dans les deux premi`eres parties (syst`emespolynomiaux et non polynomiaux) du site. Nous avonsajout?e Brent,Butcher,Direct Kin. et Virasaro quiproviennent de la partie appel?ee probl`emes difficiles.Toutes les strat?egies de r?esolution utilisent commechoix de variable le tour de r^ole. Entre deux bran-chements dans l’arbre de recherche, trois proc?eduressont appel?ees en s?equence. D’abord, un test d’exis-tence utilisant la monotonie, am?elior?e par le regroupe-ment d’occurrences, v?erifie que l’image de chaque fonc-tion contient z?ero3. Ensuite, le contracteur est appel?e :Mohc,3BCID(Mohc), ou l’un des concurrents cit?es. En-fin, l’algorithme Newton sur intervalles est appel?e si labo^?te courante a un diam`etre de 10 ou moins. Tous lesparam`etres ont ?et?e fix?es `a des valeurs par d?efaut. Leratio de pr?ecision du rognage dans 3B et Box est 10% ;une contrainte est mise dans la queue de propagationsi l’intervalle d’une de ses variables est r?eduit de plusde plus de τpropag = 1% avec tous les contracteurs sauf3BCID(HC4) et 3BCID(Mohc) (10%). Pour Mohc, le pa-ram`etre τmohc a ?et?e fix?e `a 70% ou 99%.?vaut 3% dans Mohc et 10% dans 3BCID(Mohc).5.1 R?esultatsLe tableau 1 compare le temps CPU utilis?e etle nombre de points de choix obtenus par Mohc et3BCID(Mohc) avec ceux obtenus par leurs concurrents.La derni`ere colonne donne le gain obtenu par Mohc, c.-`a-d. Gain =tempsC P U (meilleur comp ?etiteur)tempsCP U (meilleure strat ?egie de ty pe M ohc)Le tableau montre les tr`es bons r?esultats obte-nus par Mohc, en termes de pouvoir de filtrage (pe-tit nombre de points de choix) et de temps CPU.Les r?esultats obtenus par 3BCID(Box),Octum et3BCID(Octum) ne sont pas indiqu?es car ces m?ethodesne se sont pas av?er?ees comp?etitives avec Mohc. Parexemple, Octum est moins rapide que Mohc d’un ordrede grandeur. La sup?eriorit?e de Mohc sur Box montrequ’il vaut mieux un plus grand effort de filtrage (appel`a BoxNarrow) moins souvent, c.-`a-d. quand on a d?e-tect?e qu’une variable ?etait monotone. Mohc et HC4 ob-tiennent des r?esultats similaires sur 9 des 17 probl`emestest?es. Avec τmohc = 70%, on peut noter que la perteen performance de Mohc (resp. 3BCID(Mohc)) par rap-port `a HC4 (resp. 3BCID(HC4)) sur ces probl`emes estn?egligeable. Elle est inf?erieure `a 5%, sauf pour Katsura(25%).Sur 6 NCSP, Mohc obtient un gain compris entre 2.4et 8. Sur Butcher et Direct kin., on observe m^emeun gain de resp. 163 et 49. Sans le test d’existence par3Ce test d’existence ne prend qu’une petite part du tempstotal (en g?en?eral moins de 10% et moins de 1% pour 3BCID),tout en am?eliorant grandement la performance des concurrents.
Tab. 1 – R?esultats exp?erimentaux. La premi`ere colonne inclut le nom du syst`eme, le nombre d’?equations et le nombrede solutions. Les autres colonnes donnent le temps CPU en secondes (en haut) et le nombre de points de choix (en bas)pour tous les comp?etiteurs. Les meilleurs temps sont en gras.NCSP HC4 Box 3BCID(HC4) Mohc 70% Mohc 99% 3BCID(Mohc) 70% 3BCID(Mohc) 99% GainButcher &4e+5 &4e+5 282528 &4e+5 &4e+5 5431 1722 1638 3 1.8e+8 2.2e+6 288773 623Directkin. &2e+4 &2e+4 17507
428 356 49.111 2 1.4e+6 777281 730995 8859 Virasoro &2e+4 &2e+4 7173
1051 897 8.008 224 2.5e+6 805047 53 38389 66.8Yamam.1 32.4 12.6 11.7 19.2 27.0 2.2 2.87 5.308 7 29513 3925 3017 24767 29973 345 295 10.2Geneig
390 463 435 107 81.1 4.816 10 4.1e+6 1.3e+6 161211 799439 655611 13909 6061 26.6Hayes 163 323 41.6 30.9 27.6 17.0 13.8 3.028 1 253 17763 73317 49059 4375 1679 10.6Trigo1 93 332 151 30 30.6 57.7 73.2 3.1010 9 5725 6241 2565 1759 1673 459 443 5.79Fourbar 863 2441 1069 361 359 366 373 2.404 3 1.6e+6 1.1e+6 965343 437959 71 45561 21.2Pramanik 26.9 91.9 35.9 30.3 25.0 20.8 21.3 1.293 2 65 69259 87961 69637 12691 Caprasse 2.04 11.5 2.73 1.87 2.69 2.64 4.35 1.094 18 7671 5957 1309 4577 3741 867 383 3.42Kin1 6.91 26.9 1.96 5.68 5.65 1.79 3.43 1.096 16 1303 689 87 1055 931 83 83 1.05Redeco8
6.28 3529 2936 6.10 10.65 1.038 8 1.0e+7 7.9e+6 2441 6.8e+6 4.6e+6 2211 1489 1.64Trigexp2 1610 &2e+4 86.9
87 165 1.0011 0 1.6e+6 14299 1417759 935227 14299 Eco9 39.9 94.1 13.9 46.8 44.2 14.0 26.6 0.999 16 423 6193 97961 84457 6025 4309 1.44I5 9310 &2e+4 55.9 7107 7129 57.5 84.1 0.9710 30 2.4e+7 10621 1.6e+7 1.5e+7 9773 Brent 497 151 18.9 244 232 19.9 41.4 0.9510 e+6 23855 3923 752533 645337 3805 3189 1.23Katsura 182 2286 77.8 106 143 104 251 0.7512 7 727 4251 98779 94249 3573 3471 1.22monotonie appel?e avant les contracteurs, on a obtenuun gain de 37 sur le syst`eme Fourbar.En conclusion, la combinaison 3BCID(Mohc) semble^etre tr`es prometteuse.5.2 Travaux connexesUn algorithme de propagation de contraintes exploi-tant la monotonie se trouve dans le r?esolveur par inter-valles ALIAS4. Sa proc?edure de r?evision n’utilise pasun arbre pour repr?esenter une expression f(contrai-rement `a HC4-Revise). A la place, une fonction deprojection foproj est cr?e?ee pour r?eduire l’intervalle dechaque occurrence oet est ?evalu?ee avec une extensionpar monotonie [foproj ]M. C’est plus co^uteux que Min-MaxRevise et n’est pas optimal puisqu’aucune proc?e-dure MonotonicBoxNarrow n’est utilis?ee.L’article [5] d?ecrit un algorithme de propagation4www-sop.inria.fr/coprin/logiciels/ALIAS/ALIAS.htmlde contraintes appel?e Octum.Mohc et Octum ont ?et?econ,cus ind?ependamment pendant le premier semestrede 2009. Pour le d?ecrire rapidement, Octum appelleMonotonicBoxNarrow quand toutes les variables de lacontrainte sont monotones. Compar?e `a Octum :–Mohc ne demande pas qu’une fonction soit mono-tone par rapport `a toutes ses variables simultan?e-–Mohc utilise MinMaxRevise pour contracter rapi-dement les intervalles des variables (de Y) appa-raissant une seule fois (voir la proposition 4) ;–Mohc utilise un algorithme de regroupement d’oc-currences pour d?etecter plus de cas de monotonie.Une premi`ere ?etude exp?erimentale (non d?ecrite ici)montre que la bien meilleure performance de Mohcest due principalement `a la condition ?etablie dans lelemme 3 (et test?ee durant MinMaxRevise), qui permetd’?eviter des appels `a LeftNarrowFmax et `a ses proc?e-dures sym?etriques.
6 ConclusionCet article a pr?esent?e un algorithme de propagationde contraintes utilisant la monotonie des fonctions. Enutilisant les ingr?edients pr?esents dans les proc?eduresexistantes HC4-Revise et BoxNarrow,Mohc a le po-tentiel pour remplacer avantageusement HC4 et Box,comme le montrent nos premi`eres exp?erimentations.De plus, 3BCID(Mohc) semble constituer une combi-naison tr`es prometteuse.La proc?edure Mohc-Revise utilise deux param`etresutilisateurs, notamment τmohc pour r?egler la sensibilit?e`a la monotonie. Un travail futur consistera `a rendreMohc-Revise auto-adaptatif en permettant de r?eglerautomatiquement τmohc durant la recherche combina-toire.R?ef?erences[1] I. Araya. Exploiting Common Subexpressionsand Monotonicity of Functions for Filtering Al-gorithms over Intervals. PhD thesis, Universit?ede Nice–Sophia, 2010.[2] I. Araya, B. Neveu, and G. Trombettoni. Unenouvelle extension de fonctions aux intervalles ba-s?ee sur le regroupement d’occurrences. In Proc.JFPC, 2010.[3] F. Benhamou, F. Goualard, L. Granvilliers, andJ.-F. Puget. Revising Hull and Box Consistency.In Proc. ICLP, pages 230–244, 1999.[4] G. Chabert. www.ibex-lib.org, 2010.[5] G. Chabert and L. Jaulin. Hull Consistency Un-der Monotonicity. In Proc. CP, LNCS 5732, pages188–195, 2009.[6] G. Chabert, G. Trombettoni, and B. Neveu. Box-Set Consistency for Interval-based ConstraintProblems. In Proc. SAC (ACM), pages 1439–.[7] H. Collavizza, F. Delobel, and M. Rueher. Com-paring Partial Consistencies. Reliable Computing,5(3) :213–228, 1999.[8] A. Goldsztejn, C. Michel, and M. Rueher. Effi-cient Handling of Universally Quantified Inequa-lities. Constraints, 14(1) :117–135, 2009.[9] M. Kieffer, L. Jaulin, E. Walter, and D. Meizel.Robust Autonomous Robot Localization UsingInterval Analysis. Reliable Computing, 3(6) :337–361, 2000.[10] V. Kreinovich, A.V. Lakeyev, J. Rohn, and P.T.Kahl. Computational Complexity and Feasibilityof Data Processing and Interval Computations.Kluwer, 1997.[11] O. Lhomme. Consistency Techniques for NumericCSPs. In Proc. IJCAI, pages 232–238, 1993.[12] J-P. Merlet. Interval Analysis and Robotics. InSymp. of Robotics Research, 2007.[13] R. E. Moore. Interval Analysis. Prentice-Hall,1966.[14] G. Trombettoni and G. Chabert. ConstructiveInterval Disjunction. In Proc. CP, LNCS 4741,pages 635–650, 2007.[15] P. Van Hentenryck, L. Michel, and Y. Deville. Nu-merica : A Modeling Language for Global Optimi-zation. MIT Press, 1997.
CitationsCitations1ReferencesReferences15ABSTRACT: Quand une fonction f est monotone par rapport à une variable sur un domaine donné, il est bien connu que l'extension aux intervalles par monotonie de f calcule une image plus étroite que l'extension naturelle. Cet article présente une nouvelle extension aux intervalles d'une fonction f appelée regroupement d'occurrences et noté [f ]og . Quand f n'est pas monotone par rapport à une variable x sur un domaine donné [B], nous essayons de transformer f en une nouvelle fonction f og qui est monotone sur deux variables xa et xb , qui regroupent des occurrences de x de telle sorte que f og soit croissante par rapport à xa et décroissante par rapport à xb . [f ]og est l'extension aux intervalles par monotonie de f og et produit une image plus étroite que l'extension naturelle. Pour trouver un bon regroupement d'occurrences, nous proposons un programme liné?aire et un algorithme qui minimisent une surestimation du diamètre de l'image de [f ]og basé sur une forme de Taylor de f . Finalement, des expé?rimentations montrent les avantages de cette nouvelle extension lors de la résolution de systèmes d'é?quations. Full-text · Article · Jun 2010 ArticleOctober 2008 · International Journal of Artificial Intelligence Tools · Impact Factor: 0.39When handling 2D packing problems, numerous incomplete and complete algorithms maintain a so-called bottom-left (BL) property: no rectangle placed in a container can be moved more left or bottom. While it is easy to make a rectangle BL when it is added in a container, it is more expensive to maintain all the placed pieces BL when a rectangle is removed. This prevents researchers from designing... Conference PaperAugust 2011Researchers from interval analysis and constraint (logic) programming communities have studied intervals for their ability to manage infinite solution sets of numerical constraint systems. In particular, inner regions represent subsets of the search space in which all points are solutions. Our main contribution is the use of recent and new inner region extraction algorithms in the upper... Conference PaperJuly 2010We propose in this paper a new interval constraint propagation algorithm, called MOnotonic Hull Consistency (Mohc), that exploits monotonicity of functions. The propagation is standard, but the Mohc-Revise procedure, used to filter/contract the variable domains w.r.t. an individual constraint, uses monotonic versions of the classical HC4-Revise and BoxNarrow procedures. Mohc-Revise appears to... Conference PaperSeptember 2009When interval methods handle systems of equations over the reals, two main types of filtering/contraction algorithms are used to reduce the search space. When the system is well-constrained, interval Newton algorithms behave like a global constraint over the whole n ×n system. Also, filtering algorithms issued from constraint programming perform an AC3-like propagation loop, where the... Data provided are for informational purposes only. Although carefully collected, accuracy cannot be guaranteed. Publisher conditions are provided by RoMEO. Differing provisions from the publisher's actual policy or licence agreement may be applicable.This publication is from a journal that may support self archiving.}