Using SAT Encodings to Derive CSP Value Ordering H

UsingSATEncodingstoDeriveCSPValueOrderingHeuristicsChristopheLecoutre,LakhdarSais,andJulienVionCRIL-CNRSFRE2499,Universit´ed’ArtoisLens,Franceflecoutre;sais;[e-mail],weaddresstheissueofvalueorderingheuristicsinthecontextofabacktrackingsearchalgorithmthatexploitsbinarybranchingandtheadaptivevariableorderingheuristicdom=wdeg.Ourinitialexperimentationonrandominstancesshowsthat(inthiscontext),contrarytogeneralbelief,follow-ingthefail-firstpolicyinsteadofthepromisepolicyisnotreallypenalis-ing.Furthermore,usingSATencodingsofCSPinstances,anewvalueorderingheuristicrelatedtothefail-firstpolicycanbenaturallyderivedfromthewell-knownJeroslow-Wangheuristic.Thisheuristic,calledmin-inverse,exploitsthebi-directionalityofconstraintsupportstogiveamorecomprehensivepictureintermsofdomainreductionwhenagivenvalueisassignedto(resp.removedfrom)agivenvariable.AnextensiveexperimentationonawiderangeofCSPinstancesshowsthatmin-inversecanoutperformtheotherknownvalueorderingheuris-tics.1IntroductionForsolvinginstancesoftheConstraintSatisfactionProblem(CSP),backtrackingsearchalgorithmsarecommonlyused.Tolimittheircombinatorialexplosion,variousim-provementshavebeenproposed(e.g.orderingheuristics,filteringtechniquesandcon-flictanalysis).Itiswellknownthattheorderingusedtoperformsearchdecisionshasagreatimpactonthesizeofthesearchtree.Ateachstage,oneneedstodecidethevaluetoassigntoavariable.Sofar,suchdecisionshavebeenperformedbychoosingthevariableinafirststep(verticalselection)andthevaluetoassigninasecondstep(horizontalselection).Manyworkshavebeendevotedtothefirstselectionstep.Variableorderingheuris-ticsthathavebeenproposedcanbeconvenientlyclassifiedasstatic(e.g.deg),dynamic(e.g.dom[15],bz[6],dom=ddeg[4])andadaptive(e.g.dom=wdeg[5]).Theheuristicdom=wdeghasbeenshownsuperiortotheotherones[5,21,16,28].However,valueordering(thesecondstepofthedecision)hasclearlybeenconsideredforalongtimeaspotentiallyofmarginaleffecttosearchimprovements.Theargumentsbehindthiscanberelatedtothefactthatselectingagivenvalueiscomputationallymoredifficultthanselectingagivenvariable,particularlywhenoneconsidersdynamicselection.Thesecondreasonforconsideringvalueorderingasuselessisthat,whenfacingunsatisfi-ableinstancesorwhensearchingallsolutions,oneneedstoconsiderallvaluesforeachvariable.AsclearlyshownbySmithandSturdy[26],theseargumentsholdwhensearchisbasedond-waybranchingbutnoton2-waybranching.d-waybranchingmeansthat,ateachnodeofthesearchtree,avariablexisselectedanddbranchesareconsideredwheredisthecurrentsizeofthedomainofx:theithbranchcorrespondstox=aiwhereaidenotestheithvalueofthedomainofx.Ontheotherhand,withbinary(or2-way)branching,ateachnodeofthesearchtree,apair(x,a)isselectedwherexisanunassignedvariableandaavalueinthedomainofx,andtwobranchesareconsidered:thefirstonecorrespondstotheassignmentx=aandthesecondonetotherefutationx6=a.Thesetwoschemesarenotequivalentasithasbeenshownthatbinarybranchingismorepowerfulthannon-binarybranching[17].Traditionally,twoprinciplesareconsideredduringsearch:ateachstep,selectthevariablewhichisthemostconstrainedandselectthentheleastconstrainedvalue(e.g.min-conflicts[12]).Theseprinciplesrespectivelycorrespondtotwopoliciescalledfail-firstandpromise,andoneinterestingissueistheadherenceassessmentofheuristicstobothpolicies[2,29].Inthispaper,wefocusonvalueorderingheuris-tics,andmoreprecisely,wetrytodetermineifvalueorderingheuristicsshouldadhereinprioritytothepromisepolicy.Ofcourse,onecanbesurprisedthatweaddressthisissueasitiscommonlyadmittedthatitshouldbethecase.Inparticular,alotofworkssupporttheideathatavaluemustbechosenbyestimatingthenumberofsolutionsorconflicts.Onehasthentopreferthevaluethatmaximizestheestimatednumberofsolu-tionsintheremainingnetwork[8,13,24,20]orminimizesthenumberofconflictswithvariablesintheneighbourhood[12,23].However,wenoticedthatmostoftheexperimentalresultsaregivenwhend-waybranchingand/ornonadaptivevariableheuristics(suchasdom,bz,dom=ddeg)areused.ThisisthereasonwhywedecidedtosolveawiderangeofrandomCSPin-stancesusingtheMACalgorithm,i.e.thealgorithmthatmaintainsarcconsistencyduringsearch[25].Wetestedbothbranchingschemesandbothdynamicandadap-tivevariableorderingheuristicson7classesofbinaryinstancessituatedatthephasetransitionofsearch.Foreachclasshn,d,e,ti,definedasusually,50instanceshavebeengenerated.Moreprecisely,thenumberofvariablesnhasbeensetto40,thedomainsizedbetween8and180,thenumberofconstraintsebetween753and84(and,sothedensitybetween0:96and0:1)andthetightnesst(whichdenotesheretheprob-abilitythatapairofvaluesisallowedbyarelation)between0:1and0:9.Thefirstclassh40,8,753,0:1icorrespondstodenseinstancesinvolvingconstraintsoflowtight-nesswhereastheseventhoneh40,180,84,0:9icorrespondstosparseinstancesinvolvingconstraintsofhightightness.Whatisinterestinghereisthatasignificantsamplingofdomainsizes,densitiesandtightnessesisconsidered.InTables1and2,wecanobservetheresultsthatwehaveobtainedwiththeclassicalvalueorderingheuristicmin-conflictsandthe“anti”heuristicmax-conflicts1iden-tifiedasconfts.Heremin-conflictscorr