CHRISTIANSCHULTE
SchoolofInformationandCommunicationTechnology,
KTH–RoyalInstituteofTechnology,Isafjordsgatan39,Electrum229SE-140Kista,SWEDEN,email:cschulte@kth.se.PETERJ.STUCKEY
NICTAVictoriaLaboratory,DeptofComp.Sci.&Soft.Eng.,
UniversityofMelbourne3010,AUSTRALIA,
email:pjs@cs.mu.oz.au.
Abstract
Thispaperpresentsamodelandimplementationtechniquesforspeed-ingupconstraintpropagation.Threefundamentalapproachestoimprov-ingconstraintpropagationbasedonpropagatorsasimplementationsofconstraintsareexplored:keepingtrackofwhichpropagatorsareatfix-point,choosingwhichpropagatortoapplynext,andhowtocombineseveralpropagatorsforthesameconstraint.
Weshowhowidempotencereasoningandeventshelptrackfixpointsmoreaccurately.Weimprovethesemethodsbyusingthemdynamically(takingintoaccountcurrentdomainstoimproveaccuracy).Wedefinepriority-basedapproachestochoosinganextpropagatorandshowthatdynamicprioritiescanimprovepropagation.Weillustratethattheuseofmultiplepropagatorsforthesameconstraintcanbeadvantageouswithpriorities,andintroducestagedpropagatorsthatcombinetheeffectsofmultiplepropagatorswithprioritiesforgreaterefficiency.
1Introduction
WeconsidertheproblemofsolvingConstraintSatisfactionProblems(CSPs)definedinthesenseofMackworth[21],whichcanbestatedbrieflyasfollows:
Wearegivenasetofvariables,adomainofpossiblevaluesforeachvariable,andaset(readasconjunction)ofconstraints.Eachcon-straintisarelationdefinedoverasubsetofthevariables,limitingthecombinationofvaluesthatthevariablesinthissubsetcantake.Thegoalistofindaconsistentassignmentofvaluestothevariablessothatalltheconstraintsaresatisfiedsimultaneously.
1
Onewidely-adoptedapproachtosolvingCSPscombinesbacktrackingtreesearchwithconstraintpropagation.Thisframeworkisrealizedinfinitedomaincon-straintprogrammingsystems,suchasSICStusProlog[18],ILOGSolver[17],andGecode[12]thathavebeensuccessfullyappliedtomanyreal-lifeindustrialapplications.
Atthecoreofafinitedomainconstraintprogrammingsystemisaconstraintpropagationenginethatrepeatedlyexecutespropagatorsfortheconstraintsofaproblem.Propagatorsdiscoverandremovevaluesfromthedomainsofvariablesthatcannolongertakepartinasolutionoftheconstraints.
Example1.1ConsiderasimpleCSP,withvariablesx1,x2,andx3whosedomainofpossiblevaluesarerespectivelyx1∈{2,3,4},x2∈{0,1,2,3},x3∈{−1,0,1,2}andtheconstraintsarex3=x2,x1≤x2+1,andx1=3.
Apropagatorforx3=x2candeterminethatx2=3inanysolutionofthisconstraintsincex3cannottakethevalue3.Similarlyx3=−1.Thepropagatorthenreducesthedomainsofthevariablestox2∈{0,1,2}andx3∈{0,1,2}.Apropagatorforx1≤x2+1candeterminethatx1=4sincex2≥3,andx2=0sincex1≤1sothedomainsarereducedtox1∈{2,3}andx2∈{1,2}.Thepropagatorforx1=3canremovethevalue3fromthedomainofx1,leavingx1∈{2}(orx1=2).Ifwenowreconsiderthepropagatorforx3=x2wecanreducedomainstox2∈{1,2}andx3∈{1,2}.Nopropagatorcanremoveanyfurthervalues.
Wehavenotsolvedtheproblem,sincewedonotknowavalueforeachvari-able.Soafterpropagationweapplysearch,usuallybysplittingthedomainofavariableintotwodisjointsubsetsandconsideringtheresultingtwosubproblems.Supposewesplitthedomainofx2.Onesubproblemhasx1∈{2},x2∈{1}andx3∈{1,2}.Applyingthepropagatorforx2=x3resultsinx3∈{2}.Sinceeachvariablenowtakesafixedvaluewecancheckthatx1=2,x2=1,x3=1isasolutiontotheCSP.Theothersubproblemhasx1∈{2},x2∈{2}andx3∈{1,2},andleadstoanothersolution.2Ascanbeseenfromtheexamplefinitedomainconstraintprogramminginterleavespropagationwithsearch.Inthispaperweinvestigatehowtomakeapropagationengineasefficientaspossible.
Therearetwoimportantdecisionstheenginemustmake:whichpropagatorsshouldexecute,andinwhichordertheyshouldexecute.Inordertomakeconstraintpropagationefficient,itisclearthattheengineneedstotakethefollowingissuesintoaccount:avoidunnecessarypropagatorexecution,restrictpropagationtorelevantvariables,andchoosethecheapestpossiblemethodforpropagation.Inthispaperweshowhowpropagationcanbespeededupiftheenginetakestheseissuesintoaccount.
Thecontributionsofthepaperareasfollows:•Wegiveaformaldefinitionofpropagationsystemsincludingfixpointandevent-basedoptimizationsusedincurrentpropagationsystems.
•Weextendevent-basedpropagationsystemstousedynamicallychangingeventsets.
2
•Weintroducemultiplepropagatorsandstagedpropagatorsforasingleconstraintforusewithpropagationqueueswithpriority.
•Wegiveexperimentalresultsthatclarifytheimpactofmanychoicesinim-plementingpropagationengines:includingidempotencereasoning,staticanddynamicevents,basicqueuingstrategies,priorityqueues,andstagedpropagation.
PlanofthepaperThenextsectionintroducespropagation-basedconstraintsolving,followedbyamodelforconstraintpropagationsystemsinSection3.Section4presentshowtooptimizepropagationbytakingidempotenceintoac-count,whileSection5explorestheuseofeventsets.WhichpropagatorshouldbeexecutednextisdiscussedinSection6,whilecombinationstrategiesofmul-tiplepropagatorsforthesameconstraintisdiscussedinSection7.Experimentsforeachfeatureareincludedintherelevantsection,andasummaryisgiveninSection8.Section9concludes.
2Propagation-basedConstraintSolving
Thissectiondefinesourterminologyforthebasiccomponentsofaconstraintpropagationengine.Inthispaperwerestrictourselvestofinitedomainintegerconstraintsolving.Almostallthediscussionappliestootherformsoffinitedomainconstraintsolvingsuchasforsetsandmultisets.
DomainsAdomainDisacompletemappingfromafixed(finite)setofvariablesVtofinitesetsofintegers.AfalsedomainDisadomainwithD(x)=∅forsomex∈V.Avariablex∈VisfixedbyadomainD,if|D(x)|=1.TheintersectionofdomainsD1andD2,denotedD1⊓D2,isdefinedbythedomainD(x)=D1(x)∩D2(x)forallx∈V.
AdomainD1isstrongerthanadomainD2,writtenD1⊑D2,ifD1(x)⊆D2(x)forallx∈V.AdomainD1isstrongerthan(equalto)adomainD2w.r.t.variablesV,denotedD1⊑VD2(resp.D1=VD2),ifD1(x)⊆D2(x)(resp.D1(x)=D2(x))forallx∈V.
Arangeisacontiguoussetofintegers,weuserangenotation[l..u]todenotetherange{d∈Z|l≤d≤u}whenlanduareintegers.AdomainisarangedomainifD(x)isarangeforallx.LetD′=range(D)bethesmallestrangedomaincontainingD,thatis,theuniquedomainD′(x)=[infD(x)..supD(x)]forallx∈V.
Weshallbeinterestedinthenotionofaninitialdomain,whichwedenoteDinit.Theinitialdomaingivestheinitialvaluespossibleforeachvariable.ItallowsustorestrictattentiontodomainsDsuchthatD⊑Dinit.
ValuationsandconstraintsAnintegervaluationθisamappingofvariablestointegervalues,written{x1→d1,...,xn→dn}.Weextendthevaluationθtomapexpressionsandconstraintsinvolvingthevariablesinthenaturalway.
3
Letvarsbethefunctionthatreturnsthesetofvariablesappearinginavaluation.WedefineavaluationθtobeanelementofadomainD,writtenθ∈D,ifθ(xi)∈D(xi)forallxi∈vars(θ).
TheinfimumandsupremumofanexpressionewithrespecttoadomainDaredefinedasinfDe=inf{θ(e)|θ∈D}andsupDe=sup{θ(e)|θ∈D}.WecanmapavaluationθtoadomainDθasfollows
{θ(x)}x∈vars(θ)
Dθ(x)=
Dinit(x)otherwiseAconstraintcovervariablesx1,...,xnisasetofvaluationsθsuchthatvars(θ)={x1,...,xn}.Wealsodefinevars(c)={x1,...,xn}.
PropagatorsWewillimplementaconstraintcbyasetofpropagatorsprop(c)thatmapdomainstodomains.Apropagatorfisamonotonicallydecreasingfunctionfromdomainstodomains:f(D)⊑D,andf(D1)⊑f(D2)wheneverD1⊑D2.ApropagatorfiscorrectforaconstraintciffforalldomainsD
{θ|θ∈D}∩c={θ|θ∈f(D)}∩c
Thisisaveryweakrestriction,forexampletheidentitypropagatoriscorrectforallconstraintsc.
AsetofpropagatorsFischeckingforaconstraintc,ifforallvaluationsθwherevars(θ)=vars(c)thefollowingholds:f(Dθ)=Dθforallf∈F,iffθ∈c.Thatis,foranydomainDθcorrespondingtoavaluationonvars(c),f(Dθ)isafixpointiffθisasolutionofc.Weassumethatprop(c)isasetofpropagatorsthatiscorrectandcheckingforc.
Theoutputvariablesoutput(f)⊆Vofapropagatorfarethevariableschangedbythepropagator:x∈output(f)ifthereexistsadomainDsuchthatf(D)(x)=D(x).Theinputvariablesinput(f)⊆VofapropagatorfisthesmallestsubsetV⊆VsuchthatforeachdomainD:D=VD′impliesthatD′⊓f(D)=output(f)f(D′)⊓D.Onlytheinputvariablesareusefulincomputingtheapplicationofthepropagatortothedomain.
Example2.1[Propagators,input,andoutput]Fortheconstraintc≡x1≤x2+1thefunctionfAdefinedbyfA(D)(x1)={d∈D(x1)|d≤supDx2+1}andfA(D)(v)=D(v),v=x1isacorrectpropagatorforc.Itsoutputvariablesare{x1}anditsinputvariablesare{x2}.LetD1(x1)={1,5,8}andD1(x2)={1,5},thenf(D1)=D2whereD2(x1)=D2(x2)={1,5}.
ThepropagatorfBdefinedasfB(D)(x2)={d∈D(x2)|d≥infDx1−1}andfB(D)(v)=D(v),v=x2isanothercorrectpropagatorforc.Itsoutputvariablesare{x2}andinputvariables{x1}.
Theset{fA,fB}ischeckingforc.ThedomainDθ1(x1)=Dθ1(x2)={2}correspondingtothesolutionθ1={x1→2,x2→2}ofcisafixpointofbothpropagators.Thenon-solutiondomainDθ2(x1)={2},Dθ2(x2)={0}correspondingtothevaluationθ2={x1→2,x2→0}isnotafixpoint(ofeitherpropagator).2
4
Apropagationsolversolv(F,D)forasetofpropagatorsFandaninitialdomainDfindsthegreatestmutualfixpointofallthepropagatorsf∈F.Inotherwords,solv(F,D)returnsanewdomaindefinedby
solv(F,D)=gfp(λd.iter(F,d))(D)
iter(F,D)=
f∈F
⊓
f(D)
wheregfpdenotesthegreatestfixpointw.r.t⊑liftedtofunctions.
Notethatbyinvertingthedirectionof⊑wecouldequallywellphrasethisasaleastfixpoint(asin[1]).Butthecurrentpresentationemphasizesthereductionofdomainsascomputationprogresses.
DomainandboundspropagatorsAconsistencynotionCgivesaconditionondomainswithrespecttoconstraints.AsetofpropagatorsFmaintainsC-consistencyforaconstraintc,ifsolv(F,D)isalwaysCconsistentforc.Manypropagatorsinpracticearedesignedtomaintainsomeformofconsistency:usuallydomainorbounds.Butnotethatmanymoredonot.
Themostsuccessfulconsistencytechniquewasarcconsistency[21],whichensuredthatforeachbinaryconstraint,everyvalueinthedomainofthefirstvariable,hasasupportingvalueinthedomainofthesecondvariablethatsat-isfiedtheconstraint.Arcconsistencycanbenaturallyextendedtoconstraintsofmorethantwovariables.Thisextensionhasbeencalledgeneralizedarccon-sistency[24],aswellasdomainconsistency[33,34](whichistheterminologywewilluse),andhyper-arcconsistency[22].AdomainDisdomainconsistentforaconstraintcifDistheleastdomaincontainingallsolutionsθ∈Dofc,thatis,theredoesnotexistD′⊏Dsuchthatθ∈D∧θ∈c→θ∈D′.Definethedomainpropagatordom(c),foraconstraintcas
dom(c)(D)(x)dom(c)(D)(x)
==
{θ(x)|θ∈D∧θ∈c}wherex∈vars(c)D(x)otherwise
Thebasisofboundsconsistencyistorelaxtheconsistencyrequirementto
applyonlytothelowerandupperboundsofthedomainofeachvariablex.Thereareanumberofdifferentnotionsofboundsconsistency[8],wegivethetwomostcommonhere.
AdomainDisbounds(Z)consistentforaconstraintcwithvars(c)={x1,...,xn},ifforeachvariablexi,1≤i≤nandforeachdi∈{infDxi,supDxi}thereexistintegersdjwithinfDxj≤dj≤supDxj,1≤j≤n,j=isuchthatθ={x1→d1,...,xn→dn}isanintegersolutionofc.
AdomainDisbounds(R)consistentforaconstraintcwithvars(c)={x1,...,xn},ifforeachvariablexi,1≤i≤nandforeachdi∈{infDxi,supDxi}thereexistrealnumbersdjwithinfDxj≤dj≤supDxj,1≤j≤n,j=isuchthatθ={x1→d1,...,xn→dn}isarealsolutionofc.
AsetofpropagatorsFmaintainsbounds(α)consistencyforaconstraintc,ifforalldomainsD,solv(F,D)isbounds(α)consistentforc.
Wecandefineabounds(Z)propagator,zbnd(c)foraconstraintcasfollows:
zbnd(c)(D)
=
D⊓range(dom(c)(range(D)))
5
search(Fo,Fn,D)
D:=isolv(Fo,Fn,D)if(Disafalsedomain)returnfalse
if(∃x∈V.|D(v)|>1)
choose{c1,...,cm}whereC∧D|=c1∨···∨cmfori∈[1..m]
if(search(Fo∪Fn,prop(ci),D))returntruereturnfalsereturntrue
Figure1:Searchprocedure
%propagation
%searchstrategy
Itisnotstraightforwardtogiveagenericdescriptionofbounds(R)propaga-tors,rbnd(c),foraconstraintc,thatjustmaintainsbounds(R)consistency.Examples3.2and4.3definethreesuchpropagators.
3ConstraintPropagationSystems
Aconstraintpropagationsystemevaluatesthefunctionsolv(F,D)duringback-trackingsearch.WeassumeanexecutionmodelforsolvingaconstraintproblemwithasetofconstraintsCandaninitialdomainD0asfollows.Weexecutetheproceduresearch(∅,F,D0)giveninFigure1foraninitialsetofpropagatorsF=∪c∈Cprop(c).Thisprocedureisusedtomakeprecisetheoptimizationspresentedintheremainderofthepaper.
Notethatthepropagatorsarepartitionedintotwosets,theoldpropaga-torsFoandthenewpropagatorsFn.Theincrementalpropagationsolverisolv(Fo,Fn,D)(tobepresentedlater)takesadvantageofthefactthatDisguaranteedtobeafixpointoftheoldpropagators.
Thesomewhatunusualdefinitionofsearchisquitegeneral.Thedefaultsearchstrategyformanyproblemsistochooseavariablexsuchthat|D(x)|>1andexplorex=infDxorx≥infDx+1.ThisiscommonlythoughtofaschangingthedomainDforxtoeither{infDx}or{d∈D(x)|d>infDx}.Thisframeworkallowsmoregeneralstrategies,forexamplex1≤x2orx1>x2.ThebasicincrementalpropagationsolveralgorithmisgiveninFigure2.ThealgorithmusesaqueueQofpropagatorstoapply.Initially,Qcontainsthenewpropagators.Eachtimethewhileloopisexecuted,apropagatorfisdeletedfromthequeue,fisapplied,andthenallpropagatorsthatmaynolongerbeatafixpointatthenewdomainD′areaddedtothequeue.Aninvariantofthealgorithmisthatatthewhilestatementf(D)=Dforallf∈F−Q.
Thepropagationsolverisolvleavestwocomponentsundefined:choose(Q)choosesthepropagatorf∈Qtobeappliednext;new(f,F,D,D′)determinesthesetofpropagatorsf′∈Fthatarenotguaranteedtobeattheirfixpointat
6
isolv(Fo,Fn,D)
F:=Fo∪Fn;Q:=Fnwhile(Q=∅)f:=choose(Q)
Q:=Q−{f};D′:=f(D)Q:=Q∪new(f,F,D,D′)D:=D′returnD
%selectnextpropagatortoapply%addpropagatorsf′∈F...
%...notnecessarilyatfixpointatD′
Figure2:Incrementalpropagationsolver.
thedomainD′.Theremainderofthepaperinvestigateshowtobestimplementthesetwocomponents.
3.1BasicVariableDirectedPropagation
Thecoreaimoftheconstraintpropagationsolversolv(F,D)istofindadomainthatisamutualfixpointofallf∈F.Theincrementalsolverisolv(Fo,Fn,D)alreadytakesintoaccountthatinitiallyDisafixpointofpropagatorsf∈Fo.Theroleofnewis(generally)toreturnasfewpropagatorsf∈Faspossible.Abasicdefinitionofnewisasfollowsnewinput(f,F,D,D′)={f′∈F|input(f′)∩{x∈V|D(x)=D′(x)}=∅}Hereallpropagatorsf′areaddedwhoseinputvariabledomainshavechanged.Bythedefinitionofinputvariables,ifnoneofthemhavechangedforf′,thenf′(D′)=D′sincef′(D)=Diff′∈F−Q.
Proposition3.1newinputmaintainstheinvariantf′(D)=Dforallf′∈F−Qatthestartofthewhileloop.
Proof:Considerf′∈F−Q.Thenf′(D)=DandifD=input(f′)D′wehavethatD′⊓f′(D)=output(f′)f′(D′)⊓D.Then
D′
==
=output(f′)=
D′⊓DD′⊓f′(D)f′(D′)⊓Df′(D′)
sinceD′⊑DsinceD=f′(D)
bydefinitionofinput(f′)sincef′(D′)⊑D′⊑D
NowD′=output(f′)f′(D′)impliesD′=f′(D′)bythedefinitionofoutput(f′).Henceeachf′inF−Qisatfixpointatthestartoftheloop.2
Theincrementalpropagationsolverisolvwiththisdefinitionofnew(assum-ingFo=∅)ismoreorlessequivalenttothepropagationalgorithmsin[4]and[1,page267].
7
Example3.2[Incrementalpropagation]Considertheproblemwithcon-straintscC≡x1=2x2andcD≡x1=3x3representedbythebounds(R)propagators
fC(D)(x1)=fC(D)(x2)=fC(D)(x)=fD(D)(x1)=fD(D)(x3)=fD(D)(x)=
D(x1)∩[2infDx2..2supDx2],D(x2)∩⌈12supDx1⌋,D(x)x∈{x1,x2}D(x1)∩[3infDx3..3supDx3],D(x3)∩⌈13supDx1⌋,D(x)x∈{x1,x3},
withinitialdomainsD(x1)=[0..17],D(x2)=[0..9],andD(x3)=[0..6].
Initiallynoconstraintisatfixpoint,soQ={fC,fD}.fCisselectedinitially,andweexecutetheboundspropagatordeterminingD(x1)=[0..16],D(x2)=[0..8].Sincex1haschanged,bothfCandfDareaddedtothequeue.ThenfDisexecutedsettingD(x1)=[0..15],D(x3)=[0..5].Againbothconstraintsarere-queued.fCisexecutedchangingthedomainstoD(x1)=[0..14],D(x2)=[0..7].ThenfDchangesthedomainstoD(x1)=[0..12],D(x3)=[0..4].Sincex1haschangedwehaveQ={fC,fD}.NowfCisexecutedfornochange,andfDisexecutedfornochange.WehavereachedafixpointD(x1)=[0..12],D(x2)=[0..6],andD(x3)=[0..4].2
4FixpointReasoning
Thepropagationenginecomputesamutualfixpointofallthepropagators.Clearly,ifwecandeterminethatsomepropagatorsareatfixpointwithoutexecutingthemwecanlimittheamountofworkrequiredbytheengine.
4.1StaticFixpointReasoning
Apropagatorfisidempotentiff(D)=f(f(D))foralldomainsD.Thatis,applyingftoanydomainDyieldsafixpointoff.
Example4.1[Idempotentpropagator]ThepropagatorfEdefinedby
fE(D)(x1)=fE(D)(x)
=
{d∈D(x1)|D(x)
33d
∈D(x1)}
x∈{x1,x2}
isthedomainpropagatorfortheconstraint3x1=2x2.ThepropagatorfEisidempotent.2Itisnotdifficulttoseethateachdomainpropagatordom(c)isidempotent.Proposition4.2ForallconstraintscanddomainsD
dom(c)(D)=dom(c)(dom(c)(D))
8
Proof:Considerθ∈cwhereθ∈D.Thenbydefinitionθ(x)∈dom(c)(D)forallx∈vars(c).Henceθ∈dom(c)(D).Sincedom(c)(D)⊑Dwehaveθ∈c∧θ∈Diffθ∈c∧θ∈dom(c)(D).Hencedom(c)(D)=dom(c)(dom(c)(D)).2Example4.3[Non-idempotentpropagators]Whilemanypropagatorsareidempotent,somewidelyusedonesarenotidempotent.Considertheconstraint3x1=2x2andthepropagatorfF:
fF(D)(x1)=D(x1)∩⌈2supx⌋D23
3
fF(D)(x2)=D(x2)∩⌈2supDx1⌋fF(D)(x)=D(x)x∈{x1,x2}Inalmostallconstraintprogrammingsystemsprop(3x1=2x2)is{fF}where
fFisthebounds(R)propagatorfor3x1=2x2.NowfFisnotidempotent.ConsiderD(x1)=[0..3]andD(x2)=[0..5].ThenD′=fF(D)isdefinedbyD′(x1)=[0..3]∩[0..⌊10/3⌋]=[0..3]andD′(x2)=[0..5]∩[0..⌊9/2⌋]=[0..4].NowD′′=fF(D′)isdefinedbyD′′(x1)=[0..3]∩[0..⌊8/3⌋]=[0..2]andD′′(x2)=[0..4]∩[0..⌊9/2⌋]=[0..4].HencefF(fF(D))=D′′=D′=fF(D).2Wecanalwayscreateanidempotentpropagatorf′fromapropagatorfbydefiningf′(D)=solv({f},D).Indeed,insomeimplementations(forexam-ple[16])prop(3x1=2x2)isdefinedasthefixpointofapplyingfF.
Assumethatidem(f)={f}iffisanidempotentpropagatorandidem(f)=∅otherwise.Thedefinitionofnewisimprovedbytakingidempotenceintoaccount
newsfix(f,F,D,D′)=newinput(f,F,D,D′)−idem(f)Anidempotentpropagatorisneverputintothequeueafterapplication.
Notethatwithouttheidempotenceoptimizationeachpropagatorfthatchangesthedomainislikelytobeexecutedagaintocheckitisatfixpoint.Al-mostallconstraintpropagationsolverstakeintoaccountstaticfixpointreason-ing(forexampleILOGSolver[17],Choco[19],SICStus[18],andGecode[12]).Somesystemsevenonlyallowidempotentpropagators(forexampleMozart[26]).
4.2DynamicFixpointReasoning
Evenifapropagatorisnotidempotentwecanoftendeterminethatf(D)isafixpointoffforaspecificdomainD.Forsimplicityweassumeafunctionfix(f,D)thatreturns{f}ifitcanshowthatf(D)isafixpointforfand∅otherwise(ofcoursewithoutcalculatingf(f(D)),otherwisewegainnothing).Inpracticethiswillbeincludedintheimplementationoff.
newdfix(f,F,D,D′)=newinput(f,F,D,D′)−fix(f,D)
Example4.4[Dynamicidempotence]Forboundspropagationforlinearequationsonrangedomainsweareguaranteedthatthepropagatorisatafix-pointifthereisnoroundingrequiredindeterminingnewendpoints[16,Theorem8].
9
Wecandefinefix(fF,D)fortheboundspropagatorfFfromExample4.3fortheconstraint3x1=2x2,asreturning{fF}ifanynewbounddoesnotrequirerounding,e.g.2infDx2/3=⌈2infDx2/3⌉or2infDx2/3≤infDx1andsimilarlyfortheotherthreebounds.
ConsiderapplyingfFtothedomainD′′fromthesameexample.NowD′′′=fF(D′′)isdefinedbyD′′′(x1)=[0..2]∩[0..⌊8/3⌋]=[0..2]andD′′′(x2)=[0..4]∩[0..⌊6/2⌋]=[0..3].Noticethatthenewboundx2≤3isobtainedwithoutrounding⌊6/2⌋=⌊3⌋=3.Inthiscaseweareguaranteedthatthepropagatorisatafixpoint.2Notethatthedynamiccaseextendsthestaticcasesinceforidempotentfitholdsthatfix(f,D)={f}foralldomainsD.Thedynamicfixpointreasoningextensionsareobviouslycorrect,givenProposition3.1.
Proposition4.5newdfixmaintainstheinvariantf(D)=Dforallf∈F−Qatthestartofthewhileloop.
Acomplexityofeitherformoffixpointreasoningisthatagreatdealofcarehastobetakenwhenweclaimapropagatorisatfixpoint,particularlyforboundspropagatorsandforpropagatorscomputingwithmultipleoccurrencesofthesamevariable.
Example4.6[Fallingintodomainholes]Consideraboundspropagatorforx1=x2+1definedas
fG(D)(x1)fG(D)(x2)fG(D)(x)
=D(x1)∩[infDx2+1..supDx2+1]=D(x2)∩[infDx1−1..supDx1−1]=D(x)x∈{x1,x2}
Wewouldexpectthispropagatortobeidempotentsincethereisnorounding
required.ConsidertheapplicationoffGtothedomainD(x1)={0,4,5,6}andD(x2)={2,3,4,5}.ThenfG(D)=D′whereD′(x1)={4,5,6}andD′(x2)={2,3,4,5}.ThisisnotafixpointforfGbecauseofthehole(thatis1,2,4∈D(x1))intheoriginaldomainofx1.2Example4.7[Multiplevariableoccurrences]Theregularconstraintin-troducedin[27]constrainsasequenceofvariablestotakevaluesdescribedbyaregularexpression(oracorrespondingfiniteautomaton).Acommoncasefortheregularconstraintistoexpresscyclicpatternsbyperformingpropagationonasequenceofvariableswheresomevariablesappearmultiply.
AssumeapropagatorfHpropagatingthatthesequenceofvariablesx1,x2,x3conformstotheregularexpression(11|00)0(thatis,thevaluesofthreevari-ablesformeitherthestring110or000).
ForadomainDwithD(x1)=D(x2)=D(x3)={0,1}propagationforthesequencex1,x2,x3isobtainedbycheckingwhichvaluesarestillpossibleforeachvariablebytraversingthesequenceonce.Inthisparticularcase,forD′=fH(D)wehavethatD′(x3)={0}andD′(x1)=D′(x2)={0,1}andD′isafixpointforfH.
10
Nowassumeasequencex1,x2,x1wherex1appearstwice.Usingthesamestrategyasabove,asingleforwardtraversalofthesequenceyields:D′=fH(D)whereD′(x1)={0}andD′(x2)={0,1}.However,D′isnotafixpointforfH.2
Thetwoexamplesabovedescribecommoncaseswhereapropagatorisnotidempotentbutinmanycasesstillcomputesafixpoint.Inthesecases,dynamicfixpointreasoningisbeneficial:staticfixpointreasoningwouldforcetheseprop-agatorstobeneverconsideredtobeatfixpointwhiledynamicfixpointreasoningallowsthepropagatortodecidewhetherthepropagatorisatfixpointforagivendomainornot.
Inpracticedynamicfixpointreasoningcompletelysubsumesstaticfixpointreasoningandiseasytoimplement.Toimplementdynamicfixpointreasoningapropagatorisextendedtonotonlyreturnthenewdomainbutalsoaflagindicatingwhetheritisguaranteedtobeatfixpoint.
4.3FixpointReasoningExperiments
Table1showsruntime(walltime)andthenumberofpropagationstepsforthethreedifferentvariantsoffixpointreasoningconsidered.Thefirstcolumnpresentsabsoluteruntimevaluesinmillisecondsandthenumberofpropagationstepswhennofixpointreasoningisconsidered.Thetworemainingcolumns“static”and“dynamic”showtherelativechangetoruntimeandpropagationstepswhenusingstaticanddynamicfixpointreasoning.Forexample,arelativechangeof+50%meansthatthesystemtakes50%moretimeorpropagationsteps,whereasavalueof−50%meansthatthesystemtakesonlyhalfthetimeorpropagationsteps.Therow“average(all)”givestheaverage(geometricmean)oftherelativevaluesforallexamples.MoreinformationontheexamplescanbefoundinAppendixAandontheusedplatforminAppendixB.
Notethatbothstaticanddynamicfixpointreasoningdonotchangethememoryrequirementsforanyoftheexamples.
StaticfixpointreasoningWhilestaticfixpointreasoningreducesthenum-berofpropagatorexecutionsby8.9%inaverage,thereductioninruntimeismodestby1.6%inaverage.Thereasonthatthereductioninpropagationstepsdoesnotdirectlytranslatetoasimilarreductioninruntimeisthattheavoidedstepstendtobecheap:afterall,thesearestepsnotperforminganypropagationasthepropagatorisalreadyatfixpoint.Exampleswithsignificantreductioninruntime(suchasdonald-d,minsort-200,picture,andsquare-5-d)profitbecausetheexecutionofcostlypropagatorsisavoided(domain-consistentlin-earequationsfordonald-dandsquare-5-d;regularpropagatorsforpicture;minimumpropagatorsinvolvingupto200variablesforminsort).Thebehaviorofgolomb-10-bandgolomb-10-disexplainedfurtherbelow.
DynamicfixpointreasoningAsexpected,bothruntimeaswellaspropa-gationstepsareconsiderablysmallerfordynamicfixpointreasoningcompared
11
Table1:Fixpointreasoningexperiments.
Example
all-interval-500bibd-7-3-60crowded-chess-7donald-dgolomb-10-bgraph-colorknights-10o-latin-7-dphotoqueens-400sequence-500square-7-bwarehouseaverage(all)
none
time(ms)steps
118.31503036
−2.0%
2279.36624.2530.371347.4835.877.46574.36108.874433.12517.9610166.24
0.74
—
1335657
−0.4%
8066
−2.5%
46
−5.9%
224
+4.5%
9344
+2.6%
48038
−11.3%
387060
−3.7%
422206
−4.1%
31424152
−1.2%
151609
−6.2%
7731557
−4.1%
2486—
−16.9%
−7.9%−5.6%
−9.1%−11.5%
−16.0%
−6.8%
−14.7%
−16.2%
−0.1%
−0.1%
−13.1%
±0.0%
±0.0%
−18.8%
−14.6%
−3.6%
−8.3%
−8.7%
−18.2%
−3.8%
+0.9%
+2.2%
−18.0%
−7.2%
−6.2%
−16.5%
+0.1%
−17.5%
−8.4%
−6.4%
−13.0%
±0.0%
−0.2%
±0.0%
−5.7%
−0.2%
−6.5%
dynamictimesteps−38.9%−24.9%
12
Table2:Fixpointreasoningexperimentswithpropagatorpriorities.
Example
all-interval-500alpha
bibd-7-3-60cars
crowded-chess-7donald-bdonald-ddonald-vgolomb-10-bgolomb-10-dgraph-colorgroceryknights-10minsort-200o-latin-7-dpartition-32photopicturequeens-400queens-400-asequence-500square-5-dsquare-7-bsquare-7-vwarehouse
static
time
−2.9%−5.4%−0.7%−0.2%−0.7%−4.8%−6.7%−5.6%−4.9%−3.3%+0.4%−4.9%±0.0%−10.9%+0.3%−8.5%−0.7%+6.5%+0.2%−1.3%+0.1%−6.4%−2.5%−6.6%−2.2%
−24.9%−15.6%−6.5%±0.0%±0.0%−22.9%−5.1%−16.5%−23.5%−23.4%±0.0%−29.5%+1.3%−9.1%−1.4%−30.4%−1.2%−13.1%±0.0%−16.2%±0.0%−11.1%−25.2%−24.9%−1.4%
−6.1%
−15.9%steps
tostaticreasoning.Thisisinparticulartrueforexamplesdonald-bandsquare-7-bwhereabounds-consistentalldifferentconstraintcantakead-vantageofreportingwhetherpropagationhascomputedafixpointduetonodomainholesasdiscussedinExample4.6(all-interval-500showsthesamebehaviorduetotheabsolutevaluepropagatorused).
InfluenceofpropagationorderSomeexamplesshowaconsiderablein-creaseinruntime(inparticular,golomb-10-bandgolomb-10-d).Thisisduetothefactthattheorderinwhichpropagatorsareexecutedchanges:costlypropagatorsareexecutedoftenwhilecheappropagatorsareexecutedlessoften(witnessedbythedecreaseinpropagationsteps).
Section6presentsprioritiesthatorderexecutionaccordingtopropagatorpriorities.Fornowitissufficienttonotethatwhenthesepriorityinversionproblemsareavoidedthroughtheuseofpriorities,thereisnoincreaseinrun-time.Table2providesevidenceforthis.Thetableshowsrelativeruntimeandpropagationsteps(relativetonofixpointreasoningasinTable1).Whenavoidingpriorityinversionitbecomesclearthatbothstaticaswellasdynamic
13
fixpointreasoningconsistentlyimprovethenumberofpropagationstepsandalsoruntime.Theonlyexceptionispicturewhereevenwithprioritiestheconsiderablereductioninexecutionstepsdoesnottranslateintoareductioninruntime.Thisispossiblyduetoachangeinpropagationorderthataffectsrun-time(thatthiscanhavearemarkableeffectevenwithprioritiesisdemonstratedinSection6).
5EventReasoning
Thenextimprovementforavoidingpropagatorstobeputinthequeueistoconsiderwhatchangesindomainsofinputvariablescancausethepropagatortonolongerbeatafixpoint.Tothisendweuseevents:aneventisachangeinthedomainofavariable.
AssumethatthedomainDchangestothedomainD′⊑D.Atypicalsetofeventsdefinedinaconstraintpropagationsystemare:
•fix(x):thevariablexbecomesfixed,thatis|D′(x)|=1and|D(x)|>1.•lbc(x):thelowerboundofvariablexchanges,thatisinfD′x>infDx.•ubc(x):theupperboundofvariablexchanges,thatissupD′x whereD′′⊑D′⊑D.SoaneventoccursonachangefromDtoD′′iffitoccursineitherthechangefromDtoD′orfromD′toD′′. GivenadomainDandastrongerdomainD′⊑D,thenevents(D,D′)isthesetofeventsφwhereφ(D,D′).SupposeD′′⊑D′⊑D,thenclearly events(D,D′′)=events(D,D′)∪events(D′,D′′). (1) Mostintegerpropagationsolversusetheeventsdefinedabove,althoughmanysystemscollapseubc(x)andlbc(x)intoasingleeventbc(x)(forexam-ple,SICStus[18],ILOGSolver[17],andGecode[12]).Choco[19]maintainsaneventqueueandinterleavespropagatorexecutionwitheventscausingmorepropagatorstobeaddedtothequeue. Otherkindsofeventsorvariantsoftheaboveeventsarealsopossible.Forexample,(fordomainsDandD′withD′⊑D): 14 •bc(x):asdiscussedabove(lbc(x)∨ubc(x)). •two(x):thevariablexreducestoadomainofatmosttwovalues:|D′(x)|≤2and|D(x)|>2. •ran(x):thevariablexreducestoadomainthatwillalwaysbearange(twoconsecutivevaluesorasinglevalue):supD′x−infD′x≤1andsupDx−infD>1. •pos(x):thevariablexreducestoadomainthatisstrictlypositive,thatisinf′Dx>0andinfDx≤0(likewise,aneventneg(x)forreductiontoastrictlynegativedomain). •nneg(x):thevariablexreducestoadomainthatisnon-negative:inf′Dx≥0andinfDx<0(likewise,aneventnpos(x)forreductiontoanon-positivedomain). •neq(x,d):thevariablexcannolongertakethevalued,thatisd∈D(x)andd∈D′(x) Theeventstwoandranareusefulfortrackingendpoint-relevanceandrange-equivalence[31].Theneqeventhasbeenusedine.g.Choco[19]andB-Prolog[37]forbuildingAC4[23]stylepropagators. Example5.2[Events]LetD(x1)={1,2,3},D(x2)={3,4,5,6},D(x3)={0,1},andD(x4)={7,8,10}whileD′(x1)={1,2},D′(x2)={3,5,6},D′(x3)={1}andD′(x4)={7,8,10}.Thenevents(D,D′)is {ubc(x1),dmc(x1),dmc(x2),fix(x3),lbc(x3),dmc(x3)} Consideringtheadditionaleventsweobtaininaddition {bc(x1),two(x1),ran(x1),bc(x3),neq(x1,3),neq(x2,4),neq(x3,0)} 2 Example5.3[Eventsaremonotonic]Eventsaremonotonic:furtherchangestoadomaindonotdiscardeventsfrompreviouschanges.Considerthepropertyrange(x)capturingthatD(x)isarangeforadomainD(thispropertyisrelatedtotheeventran(x),lackingtherestrictionthatthedomaincanhaveatmosttwoelements). Thepropertyrange(x)isnotanevent:considerdomainsD′′⊑D′⊑DwithD(x)={1,2,3,5},D′(x)={1,2,3},andD′′(x)={1,3}.Ifrangewereanevent,thenevents(D,D′′)=events(D,D′)∪events(D′,D′′).However, events(D,D′′)={dmc(x),ubc(x)} whereas events(D,D′)∪events(D′,D′′)={dmc(x),ubc(x),range(x)}∪{dmc(x)} 2 15 5.1StaticEventSets Re-executionofcertainpropagatorscanbeavoidedsincetheyrequirecertaineventstogeneratenewinformation. Definition5.4[Propagatordependence]Apropagatorfisdependentonasetofeventses(f)iff (a)foralldomainsDiff(D)=f(f(D))thenevents(D,f(D))∩es(f)=∅,(b)foralldomainsDandD′wheref(D)=D,D′⊑Dandf(D′)=D′then events(D,D′)∩es(f)=∅.Thedefinitioncapturesthefollowing.Iffisnotatafixpointthenoneoftheeventsinitseventsetoccurs.IffisatafixpointDthenanychangetoadomainthatisnotafixpointD′involvesanoccurrenceofoneoftheeventsinitsset.Notethatforidempotentpropagatorsthecase(a)neveroccurs. Forconveniencelaterwewillstoretheeventsetchosenforapropagatorfinanarrayevset[f]. Clearly,ifwekeeptrackoftheeventssincethelastinvocationofapropaga-tor,wedonotneedtoapplyapropagatorifitisnotdependentonanyoftheseevents. Example5.5[Eventsets]Eventsetsforpreviouslydiscussedpropagatorsareasfollows: fA{ubc(x2)}fB{lbc(x1)}fE{dmc(x1),dmc(x2)}fF{lbc(x1),ubc(x1),lbc(x2),ubc(x2)}Thisiseasytoseefromthedefinitionsofthesepropagators.IftheyuseinfDx thenlbc(x)isintheeventset,similarlyiftheyusesupDxthenubc(x)isintheeventset.IftheyusetheentiredomainD(x)thendmc(x)isintheeventset.2 Indexicalpropagationsolvers[34,9,6]arebasedonsuchreasoning.Theydefinepropagatorsintheformf(D)(x)=D(x)∩e(D)whereeisanindexicalexpression.Theeventsetforsuchpropagatorsisautomaticallydefinedbythedomainaccesstermsthatoccurintheexpressione. Example5.6[Indexical]Anexampleofanindexicaltopropagatex1≥x2+1is x1∈[inf(x2)+1..+∞]x2∈[−∞..sup(x1)−1]Theserangeexpressionsforindexicalsdefinetwopropagators: fI(D)(x1)fI(D)(x)fJ(D)(x2)fJ(D)(x) ==== D(x1)∩[inf(x2)+1..+∞]D(x)x=x1D(x2)∩[−∞..sup(x1)−1]D(x)x=x2 16 TheeventsetforthepropagatorfIfromthedefinitionis{lbc(x2)}whilethetheeventsetforfJis{ubc(x1)}.2Usingeventswecandefineamuchmoreaccurateversionofnewthatonlyaddspropagatorsforwhichoneoftheeventsinitseventsethasoccurred.newevents(f,F,D,D′)={f′∈F|evset[f′]∩events(D,D′)=∅}−fix(f,D)Thisversionofnew(withoutdynamicfixpointreasoning)roughlycorrespondswithwhatmostconstraintpropagationsystemscurrentlyimplement. Proposition5.7neweventsmaintainstheinvariantf(D)=Dforallf∈F−Qatthestartofthewhileloop. Proof:Considerf′∈F−Q−{f}differentfromtheselectedpropagatorf.Thenf′(D)=Dandiff′(D′)=D′thenevents(D,D′)∩es(f′)=∅bycase(b)ofthedefinitionofes(f′),sof′∈Qatthestartoftheloop. Considerselectedpropagatorf.ThisisremovedfromQ,butiff(D′)=D′thenevents(D,D′)∩es(f)=∅bycase(a)ofthedefinitionofes(f).Clearlyalsofix(f,D)=∅.Sof∈Qatthestartoftheloop.2 5.2EventSetExperiments Table3showsruntimeandnumberofpropagationstepsfordifferenteventsetsrelativetoapropagationenginenotusingevents(theengineusesdynamicfixpointreasoningbutnopriorities).Therow“average(above)”givesthegeo-metricmeanoftherelativenumbersgiveninthetablewhereas“average(all)”showstherelativenumbersforallexamples. GeneralobservationsAfirst,quitesurprising,observationisthatusingnoeventsatallisnotsobad.Itisthebestapproachfor10outofthe25benchmarksandforcrowded-chess-7byaconsiderablemargin(between8.3%and38.7%).Anothergeneralobservationisthatareductioninthenumberofpropagationstepsdoesnotdirectlytranslateintoareductioninruntime.Thisisduetothefactthatallsavedpropagatorexecutionsarecheap:thepropagatorisalreadyatfixpointanddoesnothavetoperformpropagation. Notethattheratiobetweenreductioninstepsandreductioninruntimeultimatelydependsontheunderlyingsystem.InGecode,thesystemused,theactualoverheadforexecutingapropagatorisratherlow.Insystemswithhigheroverheadonecanexpectthatthegaininruntimewillbemorepronounced.EventsetobservationsAddingthefixeventisparticularlybeneficialforbenchmarkswithmanydisequalities,particularlyqueens-400whichonlyusesdisequalities. Addingthebceventhassignificantbenefit(upto5%)whentherearelinearequalitiesasinalphaorbounds(Z)consistentalldifferentasinphoto.But 17 Table3:Eventsetexperiments(runtimeandpropagationsteps). Example all-interval-500bibd-7-3-60crowded-chess-7donald-dgolomb-10-bgraph-colorknights-10o-latin-7-dphotoqueens-400sequence-500square-7-bwarehouseaverage(all) onlyfix,dmctimesteps+0.6%±0.0% −7.3% −2.6%+8.3%±0.0%−0.6%−0.7%−12.7%−1.2%+1.6%−87.5%+2.2%−0.2%+2.2%−8.5% −16.6% +1.7% ±0.0% −2.1% ±0.0% −1.4% ±0.0% +26.4% −47.7% ±0.0% −47.5% +1.1% ±0.0% +15.1% ±0.0% +3.5% −99.1% −9.6% ±0.0% +2.7% +0.5% −1.7% +0.2%−24.3% −16.9% +4.2%−4.6% −6.6%−26.4% ±0.0% +0.7% −7.8% −38.8% +8.8% +36.3% ±0.0% −87.5% −99.1% +3.4% −2.0% −26.9% ±0.0% +1.5% −1.7% ±0.0% −7.7% −48.6% −3.5% +0.6% −49.5% −19.7% −0.5% −3.9% −9.2% −0.1% ±0.0% −0.2% +38.7% −8.4% −19.2% +7.4% −15.8% withlbc,ubctimesteps+2.0%±0.0% 18 Table4:Eventsetexperimentswithpriorities(runtimeandpropagationsteps). Exampleonlyfix,dmcwithlbc,ubctimestepstimestepsbibd-7-3-60+6.1%−3.3% +13.1%−2.5% +20.4% −0.7% donald-b+0.9%±0.0% −0.7% −9.2% +0.1% ±0.0% golomb-10-b+0.1%±0.0% −0.9% −5.5% −0.5% −7.8% minsort-200+0.9%±0.0% +1.8% ±0.0% +1.8% −1.8% picture+2.6%±0.0% +1.6% ±0.0% +3.2% ±0.0% square-7-b+0.4%−0.1%+1.2%−10.6%average(above) +1.9% −0.4% +4.8% −3.4% −7.8% −27.8%Table5:Eventsetexperimentswithpriorities(allocatedmemory). Examplebibd-7-3-60 crowded-chess-7donald-bdonald-ddonald-vgolomb-10-bgolomb-10-dminsort-200partition-32picturequeens-400queens-400-a noevents mem 6690.1198.27.83.45.839.737.732419.1160.3451.630286.6567.0 +5.4%+3.9% +5.7%+13.1%+12.8%+58.2%+34.3%+10.1%+2.8%+2.3%+9.4%+17.7%+0.2%+4.2% +20.3%+15.5% withbc mem Usingjustafixeventincreasestherequiredmemorybylessthan4%inaverage,whileusingfulleventsetsincreasestherequiredmemoryby15.5%inaverage. ItmustbenotedthatGecode(thesystemused)hasaparticularlyefficientimplementationofeventsets:theimplementationusesasinglepointerforanentryinaneventset;entriesforthesamevariableandthesamepropagatorbutwithdifferenteventsstilluseasinglepointer.Thememoryoverheadisduetothefactthatpervariableandsupportedevent,onesinglepointerforbook-keepingisneeded.Hence,thehighestoverheadcanbeexpectedforexampleswithmanyvariablesbutrelativelyfewpropagatorsandsmalleventsets(suchasbibd-7-3-60,crowded-chess-7,andpicture).Theoverheadbecomeslessnoticeableforexampleswithmanypropagatorsorlargeeventsetsandfewvari-ables(suchasqueens-400andqueens-400-a). SummaryInsummary,whilethereisacompellingargumentforfixevents,thereisonlyaweakcaseforbcbeingsupported,andlbcandubcshouldnotbeused. 5.3DynamicEventSets Eventshelptoimprovetheefficiencyofapropagation-basedsolver.Justaswecanimprovetheuseoffixpointreasoningbyexaminingthedynamiccase,wecanalsoconsiderdynamicallyupdatingeventsetsasmoreinformationisknownaboutthevariablesinthepropagator.Monotoniceventsets 20 Definition5.8[Monotonicpropagatordependence]Apropagatorfismonotonicallydependentonasetofeventses(f,D)inthecontextofdomainDiff (a)foralldomainsD0⊑Diff(D0)=f(f(D0))thenevents(D0,f(D0))∩ es(f,D)=∅,(b)fordomainsD0andD1whereD0⊑D,f(D0)=D0,D1⊑D0and f(D1)=D1thenevents(D0,D1)∩es(f,D)=∅.Clearlygiventhisdefinitiones(f,D)ismonotonicallydecreasingwithD.Thesimplestkindofeventreductionoccursbysubsumption. Definition5.9[Subsumption]ApropagatorfissubsumedfordomainD,ifforeachdomainD′⊑Dwehavef(D′)=D′. Asubsumedpropagatormakesnofuturecontribution.IffissubsumedbyDthenes(f,D)=∅andfisneverre-applied.Mostcurrentconstraintpropagationsystemstakeintoaccountpropagatorsubsumption. Example5.10[Subsumption]ConsiderthepropagatorfAandthedomainDwithD(x1)=[1..3]andD(x2)=[3..7].ThentheconstraintholdsforallD′⊑Dandes(f,D)=∅.2Changingeventsetscanoccurincasesotherthansubsumption. Example5.11[Minimumpropagator]ConsiderthepropagatorfKforx0=min(x1,x2)definedbyfK(D)(x0)fK(D)(xi)fK(D)(x) =D(x0)∩[min(infDx1,infDx2)..min(supDx1,supDx2)]=D(xi)∩[infDx0..+∞]i∈{1,2}=D(x)x∈{x0,x1,x2} Thestaticeventsetes(fK)is{lbc(x0),lbc(x1),ubc(x1),lbc(x2),ubc(x2)}.Note thatthispropagatorisidempotent. ButgivendomainDwhereD(x0)=[1..3]andD(x2)=[5..7]weknowthatmodifyingthevalueofx2willnevercausepropagation.Aminimaldefinitionofes(fK,D)is{lbc(x0),lbc(x1),ubc(x1)}.2Example5.12[exactlypropagator]Anotherexampleisapropagatorfortheexactlyconstraint[35]:exactly([x1,...,xn],m,k)statesthatexactlymoutofthevariablesx1,...,xnareequaltoavaluek.Assoonasoneofthexibecomesdifferentfromk,alleventsforxicanbeignored.Originallytheeventsaredmc(xi),1≤i≤m,lbc(m),ubc(m)anddmc(k). SupposeadomainDwhereD(k)={1,3,8}andD(x3)={2,5,6,10,11,12},thenx3=kandweknowitscontributiontotheexactlyconstraint.Wecanremovetheeventdmc(x3)fromtheeventsetsafely.2 21 Otherexamplesformonotoniceventsetsarepropagatorsforthelexcon-straintandthegeneralizedelementconstraint.Whenusingavariantofthelexpropagatorproposedin[5],eventscanberemovedassoonastheorderamongpairsofvariablesbeingcomparedcanbedecided.Forthegeneralizedelementconstraint[7]wherethearrayelementsarevariables,eventsforavariablefromthearraycanbesafelyremovedassoonasthevariablebecomesknowntobedifferentfromtheresultoftheelementconstraint. Usingmonotonicdynamiceventsetswecanrefineourdefinitionofnewasfollows. newmevents(f,F,D,D′) F′:={f′∈F|evset[f′]∩events(D,D′)}−fix(f,D)evset[f]:=es(f,D′)returnF′ Everytimeapropagatorfisapplieditseventsetisupdatedtotakeintoaccountnewlyavailableinformation. Arelatedideaisthe“typereduction”of[30]wherepropagatorsareim-provedasmoreknowledgeondomains(herecalledtypes)becomesavailable.Forexample,theimplementationofx0=x1×x2willbereplacedbyamoreefficientone,whenallelementsinD(x1)andD(x2)arenon-negative.Hereweconcentrateonhowtheeventsetschange.Thetwoideascouldbemergedastheyarecomplementary. Proposition5.13newmeventsmaintainstheinvariantf(D)=Dforallf∈F−Qatthestartofthewhileloop. Proof:TheproofisalmostidenticaltothatforProposition5.7sinceweareworkinginacontextifevset[f]=es(f,D∗)thenD⊑D∗. Forpropagatorsusingthemonotoniceventsets,wehavetheinvariantthatf∈F−Qiffevset[f]=es(f,D∗)whereD∗istheresultofthelasttimeweexecutedpropagatorf. Supposewehavef′∈F−Q−{f}wheref′(D′)=D′andf(D)=Dthenevents(D∗,D′)∩es(f,D∗)=∅andsincef′∈Qwehavethatevents(D∗,D)∩es(f,D∗)=∅otherwisewewouldhaveplacedfinthequeuealready,hencebytheequation(1)events(D,D′)∩es(f,D∗)=∅sof′∈Qatthestartoftheloop.Considerselectedpropagatorf.ThenitisremovedfromQbutiff(D′)=D′thenclearlyfix(f,D)=∅andusingcase(a)ofDefinition5.8wehavethatevents(D,D′)∩es(f,D)=∅.Hencef∈Qatthestartoftheloop.2 FullydynamiceventsetsNotethatformanypropagatorswecanbemoreaggressiveinourdefinitionofeventsetsifweallowtheeventsetstochangeinamannerthatisnotnecessarilymonotonicallydecreasing. Definition5.14[Generalpropagatordependence]Apropagatorfisde-pendentonasetofeventses(f,D)inthecontextofdomainDifforalldomainsD1whereD1⊏Dandf(D1)=D1thenevents(D,D1)∩es(f,D)=∅. 22 Usingfullydynamiceventsetswecanrefineourdefinitionofnewasfollows.newdevents(f,F,D,D′) F′:={f′∈F|evset[f′]∩events(D,D′)}−fix(f,D)if(fix(f,D)=∅)F′:=F′∪{f}evset[f]:=es(f,D′)returnF′ Everytimeapropagatorfisapplieditseventsetisupdatedtotakeintoaccountnewlyavailableinformation.Theonlydifficultcaseisthatifthedef-initionofdynamicdependencydoesnotcapturetheeventsthatoccurwhenmovingfromDtoD′=f(D).Iffixpointreasoningcannotguaranteeafixpointweneedtoaddftothequeue. Fullydynamiceventsetsaremorepowerfulthanmonotonicallydecreasingeventsets,butingeneraltheyrequirereasoningabouttheneweventsetseachtimethepropagatorisrun. Example5.15[Fullydynamiceventsforminimum]GiventhepropagatorfKfromExample5.11andthedomainDwhereD(x0)=[0..10],D(x1)=[0..15],andD(x2)=[5..10].DisafixpointoffKandaminimalsetes(fK,D)is {lbc(x0),lbc(x1),ubc(x1),ubc(x2)}WhileatD′⊑DwhereD′(x0)=[5..9],D′(x1)=[6..9],andD′(x2)=[5..10],whichisalsoafixpoint,theminimalsetes(fK,D′)is {lbc(x0),ubc(x1),lbc(x2),ubc(x2)} FortheconstraintcKwesimplyneedtomaintainalbceventforsomevariablexiintherighthandsidewiththeminimallbcvalue.2Proposition5.16newdeventsmaintainstheinvariantf(D)=Dforallf∈F−Qatthestartofthewhileloop. Proof:Wehavetheinvariantthatf∈F−Qiffevset[f]=es(f,D∗)whereD∗istheresultofthelasttimeweexecutedpropagatorf. Supposewehavef′∈F−Q−{f}wheref′(D′)=D′andf(D)=Dthenevents(D∗,D′)∩es(f,D∗)=∅andsincef′∈Qwehavethatevents(D∗,D)∩es(f,D∗)=∅otherwisewewouldhaveplacedf′inthequeuealready,hencebytheequation(1)events(D,D′)∩es(f,D∗)=∅sof′∈Qatthestartoftheloop. Considertheselectedpropagatorf.Thesamereasoningcannotapplysinceeventhoughweknowthatevents(D∗,D′)∩es(f,D∗)=∅,wehavenoguaranteethatevents(D,D′)∩es(f,D∗)isnotempty.Nowiffix(f,D)=∅thenpossiblyf(D′)=D′,butthiswillforcef∈Qbythestartoftheloop.2 EffectivelythefullydynamiceventsetsapproachreliesonlyonthedynamicfixpointreasoningofthepropagatorftohandlewhathappenswhenmovingfromDtoD′. 23 Table6:Dynamiceventsetsexperiments(withpriorities). Examplebibd-7-3-60 crowded-chess-7sequence-500o-latin-7-d +0.4%−24.0%−82.3%−0.7% monotonic time ±0.0%±0.0%−78.3%±0.0% ±0.0%−15.2%−49.5%±0.0% −41.1%−11.2% −39.3%−9.9% −19.7%−4.2% steps mem FullydynamiceventsetsarecloselyrelatedtothewatchedliteralsapproachtoimprovingunitpropagationinSATsolving[25].Usingwatchedliterals,unitpropagationonlyconsidersaclauseforpropagationifoneoftwowatchedliteralsintheclausebecomesfalse.Recently,theideaofwatchedliteralshasbeenusedinconstraintprogrammingfortheMinionsolver[13].Watchedliteralsdifferfromtheeventsweconcentrateonheresincetheytakeintoaccountvalues(similartotheneq(x,a)event).Notethatdynamiceventsetsdonotusuallyhavethepropertyofwatchedliterals,inthattheydonotneedtobeupdatedonbacktracking. 5.4DynamicEventSetsExperiments Table6showsthecomparisonofmonotonicandfullydynamiceventsetstoapropagationsolverusingstaticeventsetswith{fix,bc,dmc}eventsandpriori-tiestoavoidpriorityinversionasdiscussedbefore.Thetablelistsonlyexampleswheredynamiceventsetsareused. Thepropagatorsusingmonotoniceventsetsareasfollows:forbibd-7-3-60:lex;forcrowded-chess-7:exactlyandelement;forsequence-500:exactly;foro-latin-7-d:lex.Clearly,monotoniceventsetsleadtoadrasticreductioninbothruntimeandmemoryusage,whereitisworthnotingthatthereductionintimeisevenmoremarkedthanthereductioninpropagationsteps(eachpropagationstepbecomescheaperassmallereventsetsmustbemaintained).FullydynamiceventsetsareconsideredinBoolean-sumpropagatorsusedinbibd-7-3-60andcrowded-chess-7.Thedifferenceinimprovementbetweenthetwoexamplescanbeexplainedbythefactthatcrowded-chess-7usesBoolean-sumsasinequalitieswhilebibd-7-3-60usesBoolean-sumsasequalitieswhereinequalitiesofferthepotentialforconsiderablysmallereventsets[13].Examplebibd-7-3-60providesanotherinsight:thedrasticreductioninruntimeobservedin[13]byusingwatchedliteralsforBoolean-sumpropagatorsintheMinionsolverismostlikelynotduetosmalleventsetsbuttootheraspects.Apossibleaspectistheknowledgeaboutwhichvariableshavebeenmodifiedwhenapropagatorisexecuted. 24 Table7:Queueversusstackexperiments. Example all-interval-500alpha bibd-7-3-60cars crowded-chess-7donald-bdonald-ddonald-vgolomb-10-bgolomb-10-dgraph-colorgroceryknights-10minsort-200o-latin-7-dpartition-32photopicturequeens-400queens-400-asequence-500square-5-dsquare-7-bsquare-7-vwarehouse queue time 73.0097.312020.30 4.65553.250.6228.530.361342.483201.8433.5456.876.66141.84532.4001.2490.371583.12549.3614.4098.1232263.129491.845345.00 0.70 377777207470102016214860660525 4144036620951612091691 442222112522511343731113513939101296661119406268771126556048147840360546569636675 2075 +78.4% +61.0%steps 6WhichPropagatortoExecuteNext WenowaddresshowtodefinewhichpropagatorfinthequeueQshouldexecutefirst,thatishowtodefinethechoosefunction. ThesimplestpolicytoimplementisaFIFO(FirstInFirstOut)queueofpropagators.Propagatorsareaddedtothequeue,iftheyarenotalreadypresent,andchooseselectstheoldestpropagatorinthequeue.TheFIFOpolicyensuresfairnesssothatcomputationisnotdominatedbyasinglegroupofpropagators,whilepossiblynotdiscoveringfailure(afalsedomain)fromotherpropagatorsquickly. TheequallysimpleLIFO(LastInFirstOut)policyisastackwhereprop-agatorsnotalreadyinthestackarepushed,andchooseselectsthetopofthestack. 25 6.1BasicQueuingStrategyExperiments Table7comparesusingaFIFOqueueversusaLIFOstack.Theresult,accord-ingwithfolkloreknowledge,clearlyillustratesthataqueuemustbeused.Thefewcaseswhereastackisbetterarecomprehensivelyoutweighedbytheworstcasesforastack. LaterexperimentsinSection6.3usingprioritieswithcombinationsofFIFOqueuesandLIFOstacksrevealthatthepathologicalbehaviorofall-interval-500isduetopriorityinversion.However,thepathologicalbehaviorofminsort-200isduetotheuseofaLIFOstack. 6.2StaticPriorities Astaticallyprioritizedqueueassociateswitheachpropagatorafixedpriority,wewillassumeanintegerintherange[0..k−1].Ineffect,thequeueQissplitintokqueues,Q[0],...Q[k−1]whereeachQ[i]isaFIFOqueueforthepropagatorswithpriorityi.SelectionalwayschoosestheoldestpropagatorinthelowestnumberedqueueQ[i]thatisnon-empty.Staticprioritizationallowsonetoensurethatquickpropagatorsareexecutedbeforeslowpropagators.Wegiveanexampleofsevenstaticpriorities,withnamesoftheintegerpri-oritiesasfollows:unary=0,binary=1,ternary=2,linear=3,quadratic=4,cubic=5,andveryslow=6.Thenamesaremeanttorepresentthearityoftheconstraint,andthentheasymptoticruntimeofthepropagator,oncethecon-straintcanhandlenvariables.Sobinaryisforbinaryconstraints,quadraticisforconstraintsthatareapproximatelyO(n2)forinstanceswithnvariables.Example6.1[Propagatorpriorities]Forexample,thepropagatorfLforeven(x1)definedby sup(x)⌋fL(D)(x1)=D(x1)∩2⌈11D2 fL(D)(x)=D(x)x=x1mightbegivenpriorityunary,whilefEandfFmightbegivenprioritybinary.Thedomainpropagatordefinedin[29]forthealldifferentconstraintn2.5 ∧n))mightbegivenpriorityquadratic.i=1∧j=i+1xi=xj(withcomplexityO(n Thealldifferentbounds(Z)propagatordefinedin[28](withcomplexityO(nlogn))mightbegivenprioritylinear.2Prioritiesineffectforcemanymorefixpointstobecalculated.Afixpointofallpropagatorsatpriorityleveliandlowermustbereachedbeforeapropagatoratpriorityleveli+1isrun.Thismeanswewilloftencausemorepropagatorstorunwhenusingpriorities,butmorecheappropagators! Example6.2[Repeatedfixpoints]ConsidertheexecutionofasystemofpropagatorsforconstraintscC≡x1=2x2,cD≡x1=3x2,cM≡x2≤6→x1≤x3+7andcN≡alldifferent[x1,x2,x3,x4,x5].Wewillusethebounds(R)propagatorsfC,fD,fMforthefirstthreeconstraints,andthedo-mainpropagator,fN,foralldifferentfrom[29],forthelastconstraint.Let 26 theinitialdomainbeD(x1)=[0..18],D(x2)=[0..9],D(x3)=[0..6],andD(x4)=D(x5)=[0..3].Theprioritiesarebinary,binary,ternary,andquadraticrespectively.Allpropagatorsareatfixpoint. Supposethedomainofx1changesto[0..17].Allpropagatorsareenqued.Theprioritylevelbinarypropagatorsareruntofixpoint(asinExample3.2)givingD(x1)=[0..12],D(x2)=[0..6],D(x3)=[0..4]ThenfMissched-uledandcausesD(x1)=[0..11].BothfCandfDareenqued,andafterexecutingfC,fD,fCandfDthenextfixpointofthebinarypriorityprop-agatorsisreached:D(x1)=[0..6],D(x2)=[0..3],D(x3)=[0..2].ThenfMisscheduledagainandcausesnochange.Afterthat,fNisexecuted,itreducesthedomainsofD(x1)=[4..6]sinceallthevalues[0..3]arerequiredforthevariablesx2,x3,x4,x5.BothfCandfDareenqued,andafterexecut-ingwereachtheirfixpointD(x1)={6},D(x2)={3},D(x3)={2}.OnceagainfMisexecutedfornochange.ThenfNisexecutedoncemoreobtainingD(x4)=D(x5)={0,1}.Thisistheoverallfixpoint.2Wecanadjustthegranularityofthepriorities:wecanhaveafinerversionoftheaboveprioritieswith14priorities,eachpriorityabovewithalowandhighversion.Thisallowsustoseparate,forexample,adomainconsistentpropagatorforthebinaryabsolutevalueconstraintabs(x)=y(binary-low)fromaboundsconsistentpropagatorforthesameconstraint(binary-high).ThisincreasedgranularitywillbeimportantinSection7. Conversely,wemaycollapsetheprioritiesintofewerlevels,forexampleintothreelevelsunary-ternary,linear-quadratic,cubic-veryslow. Anothermodelforprioritiesinconstraintpropagationbasedoncompositionoperatorsis[14].Themodel,however,runsallpropagatorsoflowerprioritybeforeswitchingpropagationbacktopropagatorsofhigherpriority.Thismodeldoesnotpreemptcomputingafixpointforalowpriority.Themodelalwayscompletesafixpointforagivenprioritylevelandonlythenpossiblycontinuesatahigherprioritylevel. Mostsystemshavesomeformofstaticpriorities,typicallyusingtwoprioritylevels(forexample,SICStus[18],Mozart[26]).Thetwolevelsareoftennotentirelybasedoncost:inSICStusallindexicalshavehighpriorityandallotherlowerpriority.WhileECLiPSe[36,15]supportstwelveprioritylevels,itsfinitedomainsolveralsousesonlytwoprioritylevelswhereanotherlevelisusedtosupportconstraintdebugging. Asimilar,butmorepowerfulapproachisusedbyChoco[19]usingsevenprioritylevelsallowingbothLIFOandFIFOtraversal. Prioritizingparticularoperationsduringconstraintpropagationisimportantingeneral.Forintervalnarrowing,prioritizingconstraintscanavoidslowconvergence,seeforexample[20]. Theprioritizingofpropagatorsbycostisimportant,invertingtheprioritiescanleadtosignificantdisadvantages. Example6.3[Invertedpriorities]ConsiderexecutingExample6.2within-vertedpriorities.WefirstexecutefNthenfMfornoeffect.ThenexecutingfC 27 Table8:Priorityexperimentswithvaryinggranularities. Example all-interval-500bibd-7-3-60crowded-chess-7donald-dgolomb-10-bgraph-colorknights-10o-latin-7-dphotoqueens-400sequence-500square-7-bwarehouseaverage(all) smalltime+1.8%+0.1%+8.1%−0.1%−33.1%−1.3%−3.4%−10.6%+0.1%+0.7%+0.5%+1.3%+5.3%−5.6% steps+0.3% +1.2% +16.9% −1.5% +91.2% +0.4% ±0.0% +2.6% +33.5% −49.0% ±0.0% −5.6% −19.5% +0.5% +4.6% −38.7% +3.4% −1.5% ±0.0% +0.2% ±0.0% +0.9% ±0.0% +0.7% +13.0%+3.8% ±0.0% +5.3%−7.4% +12.0%+7.0% +23.8% −23.4% +22.0% ±0.0% +0.6% ±0.0% ±0.0% +0.5% ±0.0% −17.8% −7.3% −1.8% ±0.0% −10.6% +4.6% +1.9% −3.7% −19.9% +46.7% −0.9% −0.1% ±0.0% −31.6% +51.0% ±0.0% −5.5% +5.0% −10.5% +8.8% +91.1% ±0.0% +0.2% +16.9% time+2.3% full steps+0.3% modifiesD(x1),soeachoffNandfMareenquedandre-executedfornoeffect.ThenexecutingfDhasthesamebehavior.OverallweexecutethepropagatorsfMandfNeachatleast10times,asopposedto3and2timesrespectivelyinExample6.2.Sincetheyarethemostexpensivetoexecutewewouldexpectthistobeslower(thisisconfirmedimmediatelybelow).2 6.3StaticPriorityExperiments PrioritygranularityTable8givesruntimeandpropagationstepsofvariousprioritygranularitiescomparedtoapropagationengineusingaFIFOqueue(andusingdynamicfixpointreasoning,eventsoftypes{fix,bc,dmc},andfullydy-namiceventsets).Thethreedifferentexperimentcapturedifferentprioritygran-ularities:“small”usesthreepriorities(unary-ternary,linear-quadratic,cubic-veryslow);“medium”usessevenprioritylevels(fromunarytoveryslow);“full”uses14prioritylevels(fromunary-hightoveryslow-low). Theresultsillustratethatevenwhentherearesubstantiallymorepropaga-tions(forexample,golomb-10-{b,d})therecanbesignificantsavings.Priori- 28 tiescanhaveaverysubstantialsaving(almost50%forgolomb-10-d)andtheworstcasecostonthebenchmarksisonly10.3%.Overallwhilethe“medium”rangeofprioritiesispreferableonmanybenchmarks,the“full”rangeofpriori-tiesgivesrealspeedupsontwomorebenchmarks(photoandsquare-7-b)andtendstoreducetheworstcasebehaviorof“medium”. Examplessuchasqueens-400,queens-400-a,andsequence-500for“small”onlyfeaturepropagatorswiththesamepriority(thenumberofpropagationstepsremainsthesame).Hencetheincreaseinruntimebylessthan1%de-scribestheoverheadofusingprioritiesatall. Dependingontheunderlyingsystem,increasingthegranularityalsorequiresmorememory.Gecode,asasystembasedonrecomputationandcopying,con-stitutestheworstcaseinthateachcopiednodeinthesearchtreemaintainsqueuesforallprioritylevels.However,theaverageincreaseinused(notallo-catedasbefore)memoryis+0.2%for“small”,+0.7%for“medium”,and+1.5%for“full”andhencecanbeneglected. AbroadspectrumofprioritieswillbeusefulfortheoptimizationspresentedinSection7.Thereforeitisimportantthatwhile“full”doesnotofferhugeadvantagesover“medium”,itneitherdegradesoverallperformancenorrequiresmuchmemory. PrioritiesandstacksTable9givestheruntimeandpropagationstepsofusingprioritiestogetherwithstacksorcombinationsofstacksandqueuesforthedifferentprioritylevels.Allnumbersaregivenrelativetoapropagationengineusingthe“full”priorityspectrumwithonlyqueuesforeachprioritylevel.Allpropagationenginesconsideredalsousethefullpriorityspectrum.Thepropagationenginefor“forall”usesonlystacksforallprioritylevels,whereas“for1,2,3-ary”(“for1,2-ary”)usesstacksforprioritylevelsunary-hightoternary-low(unary-hightobinary-low)andqueuesfortheotherlevels.Thenumbersfor“forall”clarifythatthemisbehaviorofLIFOstacksisnotduetopriorityinversion.ThefolklorebeliefthatLIFOstacksaregoodforsmallpropagatorsisrefutedbythenumbersfor“for1,2,3-ary”and“for1,2-ary”.Onlythreeexamplesshowimprovementinbothcaseswhilegrocery“for1,2,3-ary”alreadyexhibitspathologicalbehavior.Themeasurementsshowthatqueueversusstackdoesnotmatterforunaryorbinaryconstraintswhereasstacksarewrongforanythingelse. IssuestoavoidTable10showsruntimeandpropagationstepsofusingpri-oritiesinflawedways.Theexperiment“completefixpoints”referstothemodelproposedin[14]wherefixpointsarealwayscompletedbeforepossiblyswitchingtoahigherprioritylevel.Astobeexpected,thenumberofpropagationstepsisreduced,howeverattheexpenseofincreasedruntime.Moreimportantly,twoexamplesexhibitingsubstantialslowdown(golomb-10-dandsquare-5-d)areparticularlyrelevantastheyfeaturepropagatorsofvastlydifferentprioritylevels. Thesurprisingbehaviorofbibd-7-3-60appearstobeduetoaproblem 29 Table9:Priorityexperimentswithstacksandpriorities. Example all-interval-500bibd-7-3-60crowded-chess-7donald-dgolomb-10-bgraph-colorknights-10o-latin-7-dphotoqueens-400sequence-500square-7-bwarehouseaverage(all) foralltimesteps−0.6%±0.0% +2.3% +5.5%+0.6%−0.6%+7.1%+62.7%+0.1%−3.3%−1.3%−0.1%+54.1%+1.7%−2.5%+23.9% +49.7% +1.2% +10.4% +1.6% +2.4% +2.5% +27.0% +7.7% +77.1% +45.8% +5.0% +2.2% +5.2% +2.2% −0.8% −1.3% −0.1% +1.2% +240.9% +1.2% +18.6% +2.9% +1.7%+36.0% ±0.0% +3.0%+0.8% +0.2%+0.2% ±0.0% +0.8% ±0.0% ±0.0% +0.8% ±0.0% ±0.0% +0.8% −0.1% +2.3% +0.1% −0.9% ±0.0% −0.4% +0.3% +7.1% +1.4% +5.0% +39.2% +1.5% ±0.0% ±0.0% +1.2% ±0.0% ±0.0% +0.3% ±0.0% −2.0% +1.7% ±0.0% ±0.0% −5.9% +1.4% for1,2-arytimesteps+0.2%±0.0% 30 Table10:Priorityexperiments:issuestoavoid. Example all-interval-500alpha bibd-7-3-60cars crowded-chess-7donald-bdonald-ddonald-vgolomb-10-bgolomb-10-dgraph-colorgroceryknights-10minsort-200o-latin-7-dpartition-32photopicturequeens-400queens-400-asequence-500square-5-dsquare-7-bsquare-7-vwarehouse completefixpoints time −0.8%+0.5%−11.7%−1.2%−4.2%+0.9%+0.9%+1.6%−2.5%+14.6%+1.9%+29.3%−0.9%+5.5%+7.3%+0.4%+1.2%−3.6%−0.7%+0.3%+0.2%+32.5%+0.5%+2.6%−3.7% ±0.0%±0.0%−45.8%−0.9%−41.1%±0.0%±0.0%±0.0%−14.5%−14.2%+0.1%−23.4%±0.0%+8.6%−3.8%−1.2%±0.0%±0.0%±0.0%±0.0%±0.0%+7.9%±0.0%±0.0%−9.0% +107.5% +18.4%steps 31 withhowtheprioritiesforthetwodifferentkindsofpropagatorsusedinthisexample(lexandBoolean-sum)areclassified.Thisclarifiesthatevenwitharichspectrumofprioritylevelsatdisposalitremainsdifficulttoassignprioritylevelstopropagators. Theexperiment“inversepriorities”showsnumbersforapropagationenginewhereapropagatorwithlowestpriorityisexecutedfirst.Theexperimentshowsthatthereisapointtotheprioritylevels,highpriority=fastpropagator.Whilethenumberofpropagationsisoftenreducedtheapproachisrarelybetterthannoprioritiesandsometimescatastrophicallyworse. Theexperiment“inversepriorities”clarifiesaveryimportantaspectofpri-orities:theynotonlyserveasameanstoimproveperformance,theyalsoserveasasafeguardagainstpathologicalpropagationorder. 6.4DynamicPriorities Asevaluationproceeds,variablesbecomefixedandpropagatorscanbereplacedbymorespecializedversions.Ifapropagatorisreplacedbyamorespecializedversion,alsoitspriorityshouldchange. Example6.4[Updatingapropagator]ConsiderthepropagatorfOforup-datingx1intheconstraintx1=x2+x3definedbyfO(D)(x1)=fO(D)(x)= D(x1)∩[infD(x2)+infD(x3)..supD(x2)+supD(x3)]D(x) x=x1 mighthaveinitialpriorityternary.Whenthevariablex2becomesfixedtod2say,thentheimplementationforx1canchangeto fO(D)(x1)=D(x1)∩[d2+infD(x3)..d2+supD(x3)] andtheprioritycanchangetobinary. 2 Changingprioritiesisalsorelevantwhenapropagatorwithn>3variableswithprioritylinear(orworse)reducestoabinaryorternarypropagator. 6.5DynamicPriorityExperiments Table11showsruntimeandpropagationstepsforanengineusingdynamicprioritiescomparedtoanengineusingalloptimizationsintroducedearlierandthefullpriorityspectrum.Dynamicallychangingthepriorityofpropagatorsastheybecomesmallerduetofixedvariablescanleadtosignificantimprovements.Ineffect,constraintsthatbecomesmaller(andthusrunathigherpriority)arerunfirstcausingthestilllargeconstraintstoberunlessoften. Thisisinparticulartrueforalphawithinitiallyonlypropagatorsforlin-earequalitieswithprioritylinear.Whenfixingvariablesduringsearchmanyofthesepropagatorsarethenrunatprioritylevelsbinaryandternary.ItisworthnotingthatusingdynamicprioritiescandisturbtheFIFOqueuebe-havior:forsequence-500itappearstobemoreimportanttorunallexactly 32 Table11:Dynamicpriorityexperiments. Examplealpha crowded-chess-7picture dynamictimesteps−25.5%−41.7%−5.0%−1.9% −26.5%±0.0% average(all)−1.7%−3.0% propagatorsatthesameprioritylevel.Runningsomeoftheexactlypropaga-torsatprioritiesbinaryandternaryisnotbeneficialanddisturbsthequeuebehavior. Dynamicprioritiesincurtheoverheadtocomputetheprioritybasedonthenumberofnotyetfixedvariables.However,theoverheadisstillsmallenoughtomakedynamicprioritiesworthwhileoverall. 7CombiningPropagation Therearemanywaystodefineacorrectpropagatorfforasingleconstraintc:theartofbuildingpropagatorsistofindgoodtradeoffsintermsofspeedofexecutionversusstrengthofpropagation.Typicallyasingleconstraintmayhaveanumberofdifferentpropagatorimplementations:thecheapestsimplepropagator,amorecomplexboundspropagator,andamorecomplexdomainpropagator,forexample. Example7.1[alldifferentpropagators]ConsiderthepropagatorfP(D)forthealldifferentconstraint. E:=∅ fori∈[1..n] if(∃d.D(xi)={d}) if(d∈E)returnD⊥elseE:=E∪{d}fori∈[1..n] if(|D(xi)|>1)D(xi):=D(xi)−EreturnD Thepropagatordoesalinearnumberofsetoperationsineachinvocationandischecking.Itcanbemadeidempotentbytestingthatnovariablebecomesfixed.AnotherpropagatorforthesameconstraintisthedomainpropagatorfNintroducedin[29]withcomplexityO(n2.5).2 33 Giventwopropagators,sayf1andf2inprop(c),wheref1isstrictlystrongerthanf2(f1(D)⊑f2(D)foralldomainsD),wecouldchoosetoimplementcbyjustf1orjustf2tradingoffpruningversusexecutiontime. Withoutprioritiesthereisnopointinimplementingtheconstraintcusingbothpropagators,sincef1willalwaysberunandalwayscomputestrongerdomainsthanf2. Wecouldpossiblymergetheimplementationofthepropagatorstocreateanewpropagatorf12(D)=f1(f2(D)).Byrunningthecheaperpropagatorimmediatelyfirstwehopethatwecan(a)quicklydeterminefailureinsomecasesand(b)simplifythedomainsbeforeapplyingthemorecomplicatedpropagatorf1.Whilethisimmediatecombinationoftwopropagatorsinessenceissimplybuildinganewpropagator,oncewehaveprioritiesinourpropagationenginewecanusetwoormorepropagatorsforthesameconstraintindifferentways. 7.1MultiplePropagators Oncewehaveprioritiesitmakessensetousemultiplepropagatorstoimplementthesameconstraint.Wecanruntheweaker(andpresumablyfaster)propagatorf2withahigherprioritythanf1.Thismakesinformationavailableearliertootherpropagators.Whenthestrongerpropagatorf1iseventuallyrun,itisabletotakeadvantagefrompropagationprovidedbyothercheaperpropagators.Notethatthisisessentiallydifferentfromhavingasinglepropagatorf12thatalwaysfirstrunsthealgorithmoff2andthenthealgorithmoff1.Example7.2[Multiplealldifferent]ConsiderthetwopropagatorsfPandfNdefinedinExample7.1above.Wecanusebothpropagators:fPwithprioritylinear,andfNwithpriorityquadratic.ThismeansthatwewillnotinvokefNuntilwehavereachedafixpointoffPandalllinearandhigherprioritypropagators. ConsidertheadditionalpropagatorfEfortheconstraint3x1=2x2,whichhasprioritybinary.ConsiderthedomainDwhereD(x1)={4,6},D(x2)={6,9},D(x3)={6,7}andD(x4)=···=D(xn)=[1..n],whichisafixpointforfE,fPandfN.Nowassumethedomainofx3isreducedto6.PropagatorfPisplacedinqueuelinearandfNisplacedinqueuequadratic.ApplyingfPremoves6fromthedomainofallthedomainsofx1,x2,x4,...,xn,andthiscausesfEtobeplacedinqueuebinary.Thisisthenextpropagatorconsideredanditcausesfailure.PropagatorfNisneverexecuted. IfwejustusefNthenweneedtoinvokethemoreexpensivefNtoobtainthesamedomainchangesasfP,andthenfail.2 7.2StagedPropagators Oncewearewillingtousemultiplepropagatorsforasingleconstraintitbecomesworthconsideringhowtomoreefficientlymanagethem.Insteadofusingtwo(ormore)distinctpropagatorswecancombinetheseveralpropagatorsintoasinglepropagatorwithmoreeffectivebehavior. 34 Weassumethatapropagatorhasaninternalstatevariable,calleditsstage.Whenitisinvoked,thestagedetermineswhatformofpropagationapplies.Example7.3[Stagedalldifferent]ConsiderthealldifferentconstraintwithimplementationsfPandfNdiscussedinExample7.1.Wecombinethemintoastagedpropagatorasfollows: •Onafix(x)event,thepropagatorismovedtostageA,andplacedinthequeuewithprioritylinear. •Onadmc(x)event,unlessthepropagatorisinstageAalready,theprop-agatorisputinstageB,andplacedinthequeuewithpriorityquadratic.•ExecutioninstageAusesfP,thepropagatorisputinstageB,andplacedinthequeuewithpriorityquadratic,unlessitissubsumed. •ExecutioninstageBusesfN,afterwardsthepropagatorisremovedfromallqueues(stageNONE). Thebehaviorofthestagedpropagatorisidenticaltothemultiplepropa-gatorsforthesampleexecutionofExample7.1.Inadditiontotheobviousadvantageofhavingasinglestagedpropagator,anotheradvantagecomesfromavoidingtheexecutionoffNwhentheconstraintissubsumed.2Inadditiontogivingotherpropagatorswithhigherprioritytheopportunitytorunbeforetheexpensivepartofastagedpropagator,thefirststageofapropagatorcanalreadydeterminethatthenextseconddoesnotneedtoberun.Thisisillustratedbythefollowingexample. Example7.4[Stagedlinearequations]ConsidertheunitcoefficientlinearequationΣni=1aixi=dconstraintwhere|ai|=1,1≤i≤n.Wehavetwoim-plementations,fQ,whichimplementsbounds(R)consistency(consideringrealsolutions,withlinearcomplexity)fortheconstraint,andfR,whichimplementsdomainconsistency(withexponentialcomplexity). Wecombinethemintoastagedpropagatorasfollows:•Onabc(x)(ordependingontheeventtypesavailable:lbc(x)orubc(x))event,thepropagatorismovedtostageA,andplacedinthequeuewithprioritylinear. •Onadmc(x)event,unlessthepropagatorisinstageAalready,thepropa-gatorisputinstageB,andisplacedinthequeuewithpriorityveryslow.•ExecutioninstageAusesfQ,afterwardsthepropagatorisputinstageB,andplacedinthequeuewithpriorityveryslow,unlesseachxihasarangedomaininwhichcaseitisremovedfromallqueues(stageNONE).•ExecutioninstageBusesfR,afterwardsthepropagatorisremovedfromallqueues(stageNONE). 35 Table12:Combinationexperiments. Exampleimmediatestagedtimestepstimestepsdonald-b+0.7%±0.0% −16.9%+10.1% ±0.0% +111.9% golomb-10-b+0.3%±0.0% −9.8% +9.2% −14.5% +8.6% graph-color−0.6%−0.6% −14.4% +12.3% −9.6% +14.3% partition-32−0.6%±0.0% −6.2% +4.2% −0.9% +7.8% picture+0.3%±0.0% −3.4% ±0.0% −38.3% +28.8% square-7-b−0.1%±0.0%−18.6%−10.9%average(above) −3.6% −0.9% −14.0% +15.3% −4.8% +6.8%nospeedup.Theonlyexceptionissquare-5-dusingbounds(R)propagationimmediatelybeforedomainpropagationforseverallinearequationpropagators.Usingmultiplepropagatorsleadstoanaveragereductioninruntimeby10%withaslowdownforjustasingleexample(graph-color).Astobeexpected,thenumberofpropagationstepsrisessharply.Thisisduetothefactthatmorepropagatorsneedtoberunandthat,similartotheintroductionofpriorities,propagatorswithhighpriorityarerunmoreoften.Theexceptionalcaseofsquare-7-bwherethenumberofpropagationstepsdecreasesappearstobeafortunatechangeinpropagationorder. Stagedpropagationoffersanotherlevelofimprovementoverusingmultiplepropagators:allexamplesnowachievespeedup.Asfewerpropagatorsmustbeexecutedcomparedto“multiple”,alsothenumberofpropagationstepsde-creases(apartfromsquare-5-dbeinganothercaseofchangingpropagationorder).Duetothereducedoverheadcomparedto“multiple”,evensmallexam-plessuchasgraph-colorareabletobenefitfromstagedexecution. Theexactimprovementinruntimeofdonald-dfor“immediate”and“staged”isduetoearlyfixpointdetectionforabiglinearequationpropagatorasdis-cussedinExample7.4. Thememoryrequirementsfor“immediate”and“staged”areunchanged.Theuseofmultiplepropagatorsfor“multiple”leadstoanaverageincreaseof6.4%inallocatedmemoryfortheexamplesshowninTable12. Insummary,stagedpropagationisveryeffectiveforallexamples,soitshouldclearlybeused. 8ExperimentSummary InTable13wesummarizetheeffectofallimprovementssuggestedinthispaper.Thenaivepropagationengineiscomparedtoanenginefeaturingalltechniquesintroducedinthispaper:dynamicfixpointreasoning,{dmc,fix,bc}fullydy-namicevents,dynamicprioritybasedLIFOqueuingwiththefullpriorityspec-trum,andstagedpropagators. Itisinterestingtonotethatallexamplesbutwarehouseshowanimprove-mentinruntimeandthatalmost75%oftheexamplesshowanimprovementofatleast10%.Theimprovementinruntimedoesnotincuralargeincreaseinmemory:thelargestincreasesareforthethreedonald-*problems,wheretheincreaseisactuallynegligibleinabsolutetermsandduetotheunderlyingmemoryallocationstrategy(asdiscussedinSection5.2). Theeffectsoftheindividualoptimizationsdiscussedinthispapercouldbesummarizedasfollows.Dynamicfixpointreasoningsubsumesstaticreasoningandiseasytoimplement,itprovidesamodestimprovementinexecutiontimes.Events,whileusedinallfinitedomainpropagationengines,havelessbenefitthanperhapswasassumedbydevelopers.Usingdynamiceventsagainleadstoamodestimprovementinexecutiontimes.ThefairnessofaFIFOqueuestrategyisessentialforschedulingpropagators.Whileprioritiesbythemselvesarenotthatimportanttheyprovideaprotectionagainstworstcasebehaviorandenable 37 Table13:Experimentsummary. Example all-interval-500alpha bibd-7-3-60cars crowded-chess-7donald-bdonald-ddonald-vgolomb-10-bgolomb-10-dgraph-colorgroceryknights-10minsort-200o-latin-7-dpartition-32photopicturequeens-400queens-400-asequence-500square-5-dsquare-7-bsquare-7-vwarehouse nooptimizations time 118.31106.562279.36 4.624.250.7030.370.381347.482430.0035.8755.417.46342.48574.368571.24108.871553.424433.1216.15517.9633391.2410166.245690.00 0.74 385.422.26688.1.7196.97.43.25.440.037.0832.47.7770.332454.5242.9160.437.0450.530286.1566.36081.543.5160.3144.229.4 −33.3% +7.2%memory 38 theuseofmultiplepropagators.Stagingisanimportantoptimizationthatcansignificantlyimproveperformance. 9ConclusionandFutureWork Wehavegivenaformaldefinitionofpropagationsystemsincludingidempotence,events,andprioritiesusedincurrentpropagationsystemsandhaveevaluatedtheirimpact.Wehaveintroduceddynamicallychangingeventsetswhichareshowntoimproveefficiencyconsiderably.Thepaperhasintroducedmultipleandstagedpropagatorswhichareshowntobeanimportantoptimizationinparticularforimprovingtheefficiencyofcostlyglobalconstraints. Whiletheimprovementstoanengineofapropagationbasedconstraintsolverhavebeendiscussedforintegerconstraints,thetechniquesreadilycarryovertoarbitraryconstraintdomainssuchasfinitesetsandmultisets. Aratherobviouswaytofurtherspeedupconstraintpropagationistocon-sidernotonlycostbutalsoestimatedimpactforapropagator.However,whilecomputingcostisstraightforwarditiscurrentlynotcleartoushowtoaccuratelypredictpropagationimpact. AExamplesUsedinExperiments Allvariantsofconstraintpropagationdiscussedinthepaperareexperimentallyevaluated.Thecharacteristicsoftheexamplesusedinevaluationaresumma-rizedinTable14.Thecolumn“variables”givesthenumberofvariablesintheexample,whereasthecolumn“propagators”showsthenumberofpropagatorsasimplementationsofconstraintsintheexample.Thecolumn“search”showswhichsearchstrategyisusedtosearchforasolution(“first”issimpleback-trackingsearchforthefirstsolution,“all”issearchforallsolutions,“best”isbranch-and-boundsearchforabestsolution).Thetwolastcolumnsdescribehowmanyfailednodesareexploredduringsearch(column“failures”)andhowmanysolutionsarefound(column“solutions”). A-dattheendoftheexamplenamemeansthatdomainpropagationisusedforalloccurringalldifferentandlinearequationconstraints.Likewise,-bmeansthatbounds(Z)propagationisusedforallalldifferentandbounds(R)foralllinearequationconstraints.Incontrast,for-vbounds(R)propagationisusedforalllinearconstraints,whereasnaivepropagation(eliminatingassignedvaluesasinExample7.1)isusedforalldifferent. Ifnototherwisementioned,boundsconsistencyisusedforarithmeticcon-straints(includinglinearconstraints)andnaivepropagationforalldifferent.•all-interval-500computesaseriesofnumberswherethedistancesbe-tweenadjacentnumbersarepairwisedistinct(prob007in[10]).Themodelusesasinglebounds(Z)consistentalldifferentpropagatorandmanybinaryabsolutevalue(abs(x)=y)andternaryminuspropagators. 39 Table14:Examplecharacteristics. Example all-interval-500alpha bibd-7-3-60cars crowded-chess-7donald-bdonald-ddonald-vgolomb-10-bgolomb-10-dgraph-colorgroceryknights-10minsort-200o-latin-7-dpartition-32photopicturequeens-400queens-400-asequence-500square-5-dsquare-7-bsquare-7-vwarehouse variables 14982611760 6016310101046201720283991471286162540040050025494981 search 07435130610730396 795791992919929 373720218816025869953242101025041272245208481301 20 solutions •alphaanddonaldarecrypto-arithmeticpuzzlesinvolvinglinearequationpropagatorsandasinglealldifferentpropagator. •bibd-7-3-60isaninstanceofabalancedincompleteblockdesignproblemwithparameters(v,k,l)=(7,3,60)(prob028in[10]).ThemodelinvolvesBoolean-sumpropagatorsandlexpropagatorsforsymmetrybreaking.•carsmodelsthewellknowncarsequencingproblemfrom[35]usingelement,exactly,andlinearequationpropagators(prob001in[10]). •crowded-chess-7placesseveraldifferentchesspiecesona7×7chess-board[11].Itusesexactly,element,domainconsistentalldifferent,andbounds(R)consistentlinearequationpropagators. •golomb-10findsanoptimalGolombrulerofsize10(prob006in[10])withtheusualmodel. •graph-colorperformsclique-basedgraphcoloringforagraphwith200nodes.Coloringeachcliqueusesadomainconsistentalldifferentprop-agator. •groceryisasmallcrypto-arithmeticpuzzleusinginparticularbounds(R)consistentmultiplicationpropagators. •knights-10findsasequenceofknightmovesona10×10chessboardsuchthateachfieldisvisitedexactlyonceandthatthemovesreturntheknighttothestartingfield.Themodelusesanaivealldifferentpropagatorandalargenumberofreifiedbinarypropagators. •minsort-200sorts200variablesusing200minimumpropagators.•o-latin-7findsanorthogonallatinsquareofsize7andmostlyusesdomainconsistentalldifferentpropagators. •partition-32partitionstwo32numberblockssuchthattheirproductsmatch.Usesseveralbounds(R)multiplicationpropagators,asingledo-mainconsistentalldifferentpropagator,andfewlinearequationprop-agators. •photoplaces9personsonapicturesuchthatasmanypreferencesaspossiblearesatisfied.Usesalargebounds(Z)consistentalldifferentpropagator,alargebounds(R)consistentlinearpropagator,andmanyreifiedbinarypropagators. •picturemodelsa25×25picture-puzzle(prob012in[10])using50regularpropagators. •queens-400andqueens-400-aplaces400queensona400×400chessboardsuchthatthequeensdonotattackeachother.queens-400usesquadraticallymanybinarydisequalitypropagators,whilequeens-400-ausesthreenaivealldifferent-propagators. 41 •sequence-500computesamagicsequencewith500elementsusing500exactlypropagators(prob019in[10]). •square-5(square-7)computesamagicsquareofsize5×5(7×7)us-inglinearequationpropagatorsandasinglealldifferentpropagator(prob019in[10]). •warehousesolvesawarehouselocationproblemfollowing[32]. BEvaluationPlatform AllexperimentsuseGecode,aC++-basedconstraintprogramminglibrary[12].Gecodeisoneofthefastestconstraintprogrammingsystemscurrentlyavailable,benchmarkscomparingGecodetoothersystemsareavailablefromGecode’swebpage.TheversionusedinthispapercorrespondstoGecode1.3.0(albeitslightlymodifiedtoeasethenumerousexperimentsinthispaper).GecodehasbeencompiledwithMicrosoftVisualStudioExpressEdition2005. AllexampleshavebeenrunonaLaptopwitha2GHzPentiumMCPUand1024MBmainmemoryrunningWindowsXP.Runtimesaretheaverageof25runswithacoefficientofdeviationlessthan4%forallbenchmarks. Acknowledgments ChristianSchulteispartiallyfundedbytheSwedishResearchCouncil(VR)undergrant621-2004-4953.WethankMikaelLagerkvistandGuidoTackformanyhelpfulsuggestionsthatimprovedthepaper. References [1]KrzysztofApt.PrinciplesofConstraintProgramming.CambridgeUniver-sityPress,Cambridge,UnitedKingdom,2003.[2]PhilippeBaptiste,ClaudeLePape,andWimNuijten.Constraint-based Scheduling.KluwerAcademicPublishers,Dordrecht,TheNetherlands,2001.[3]NicolasBeldiceanu,WarwickHarvey,MartinHenz,Fran¸coisLaburthe,Eric Monfroy,TobiasM¨uller,LaurentPerron,andChristianSchulte.Proceed-ingsofTRICS:TechniquesfoRImplementingConstraintprogrammingSys-tems,apost-conferenceworkshopofCP2000.TechnicalReportTRA9/00,SchoolofComputing,NationalUniversityofSingapore,September2000.[4]FredericBenhamou.HeterogeneousConstraintSolving.InProceedingsof theFifthInternationalConferenceonAlgebraicandLogicProgramming,volume1139ofLNCS,pages62–76,Aachen,Germany,1996.Springer-Verlag. 42 [5]MatsCarlssonandNicolasBeldiceanu.Revisitingthelexicographicorder-ingconstraint.TechnicalReportT2002-17,SwedishInstituteofComputerScience,Stockholm,Sweden,2002.[6]MatsCarlsson,GregerOttosson,andBj¨ornCarlson.Anopen-endedfinite domainconstraintsolver.InProgrammingLanguages:Implementations,Logics,andPrograms,9thInternationalSymposium,PLILP’97,volume1292ofLNCS,pages191–206,Southampton,UnitedKingdom,September1997.Springer-Verlag.[7]AndreChamard,AnnieFischler,Dominique-BenoitGuinaudeau,andAn-dreGuillard.CHIClessonsonCLPmethodology.Technicalreport,Das-saultAviation,1995.[8]ChiuWoChoi,WarwickHarvey,JimmyHo-ManLee,andPeterJ. Stuckey.Finitedomainboundsconsistencyrevisited.Technicalreport,http://arxiv.org/abs/cs.AI/0412021,2004.[9]PhilippeCodognetandDanielDiaz.Compilingconstraintsinclp(FD). JournalofLogicProgramming,27(3):185–226,June1996.[10]CSPLib.CSPLib:aproblemlibraryforconstraints,2006.Availablefrom http://www.csplib.org.[11]HenryE.Dudeney.AmusementsinMathematics.Dover,NewYork,NY, USA,1958.[12]GecodeTeam.Gecode:Genericconstraintdevelopmentenvironment,2006. Availablefromhttp://www.gecode.org.[13]IanP.Gent,ChrisJefferson,andIanMiguel.Watchedliteralsforconstraint propagationinMinion.InFr´ed´ericBenhamou,editor,TwelfthInterna-tionalConferenceonPrinciplesandPracticeofConstraintProgramming,volume4204ofLNCS,pages182–197.Springer-Verlag,Nantes,France,September2006.[14]LaurentGranvilliersandEricMonfroy.Implementingconstraintpropaga-tionbycompositionofreductions.InLogicProgramming:Proceedingsofthe19thInternationalConference,volume2916ofLNCS,pages300–314,Mumbai,India,2003.Springer-Verlag.[15]WarwickHarvey.Personalcommunication,April2004. [16]WarwickHarveyandPeterJ.Stuckey.Improvinglinearconstraintprop-agationbychangingconstraintrepresentation.Constraints,8(2):173–207,2003.[17]ILOGS.A.ILOGSolver5.0:ReferenceManual.Gentilly,France,August 2000. 43 [18]IntelligentSystemsLaboratory.SICStusProloguser’smanual,3.11.1. Technicalreport,SwedishInstituteofComputerScience,Box1263,129Kista,Sweden,2004.[19]Fran¸coisLaburthe.CHOCO:implementingaCPkernel.InBeldiceanu etal.[3],pages71–85.[20]OlivierLhomme,ArnaudGotlieb,andMichelRueher.Dynamicoptimiza-tionofintervalnarrowingalgorithms.JournalofLogicProgramming,37(1–3):165–183,1998.[21]AlanK.Mackworth.Consistencyinnetworksofrelations.ArtificialIntel-ligence,8(1):99–118,1977.[22]KimMarriottandPeterJ.Stuckey.ProgrammingwithConstraints:an Introduction.TheMITPress,Cambridge,MA,USA,1998.[23]RogerMohrandThomasC.Henderson.Arcandpathconsistencyrevisited. ArtificialIntelligence,28:225–233,1986.[24]RogerMohrandG´eraldMasini.Goodolddiscreterelaxation.InYves Kodratoff,editor,Proceedingsofthe8thEuropeanConferenceonArtificialIntelligence(ECAI88),pages651–656,Munich,Germany,1988.PitmannPublishing.[25]MatthewW.Moskewicz,ConorF.Madigan,YingZhao,LintaoZhang,and SharadMalik.Chaff:EngineeringanefficientSATsolver.InProceedingsofthe38thDesignAutomationConference,DAC2001,pages530–535,LasVegas,NV,USA,2001.ACM.[26]MozartConsortium.TheMozartprogrammingsystem,1999.Available fromwww.mozart-oz.org.[27]GillesPesant.Aregularlanguagemembershipconstraintforfinitese-quencesofvariables.InMarkWallace,editor,TenthInternationalConfer-enceonPrinciplesandPracticeofConstraintProgramming,volume3258ofLNCS,pages482–495.Springer-Verlag,Toronto,Canada,September2004.[28]Jean-Francois.Puget.Afastalgorithmfortheboundconsistencyofalldiff constraints.InProceedingsofthe15thNationalConferenceonArtificialIntelligence(AAAI-98),pages359–366,Madison,WI,USA,July1998.AAAIPress/TheMITPress.[29]Jean-CharlesR´egin.Afilteringalgorithmforconstraintsofdifferencein CSPs.InProceedingsoftheTwelfthNationalConferenceonArtificialIn-telligence,volume1,pages362–367,Seattle,WA,USA,1994.AAAIPress.[30]PierreSav´eant.Constraintreductionatthetypelevel.InBeldiceanuetal. [3],pages16–29. 44 [31]ChristianSchulteandPeterJ.Stuckey.Whendoboundsanddomain propagationleadtothesamesearchspace?TransactionsonProgrammingLanguagesandSystems,27(3):388–425,May2005.[32]PascalVanHentenryck.TheOPLOptimizationProgrammingLanguage. TheMITPress,Cambridge,MA,USA,1999.[33]PascalVanHentenryck,VijaySaraswat,andYvesDeville.Constraint processingincc(FD).Draft,1991.[34]PascalVanHentenryck,VijaySaraswat,andYvesDeville.Design,imple-mentationandevaluationoftheconstraintlanguagecc(FD).JournalofLogicProgramming,37(1–3):139–1,1998.[35]PascalVanHentenryck,HelmutSimonis,andMehmetDincbas.Constraint satisfactionusingconstraintlogicprogramming.ArtificialIntelligence,58:113–159,1992.[36]MarkWallace,StefanoNovello,andJoachimSchimpf.Eclipse:Aplatform forconstraintlogicprogramming.Technicalreport,IC-Parc,ImperialCol-lege,London,GB,August1997.[37]Neng-FaZhou.Programmingfinite-domainconstraintpropagatorsinac-tionrules.TheoryandPracticeofLogicProgramming,6(5):483–508,September2006. 45
因篇幅问题不能全部显示，请点此查看更多更全内容