A Decomposition-Based Implementation of Search Strategies

Search strategies, that is, strategies that describe how to explore search trees, have raised much interest for constraint satisfaction in recent years. In particular, limited discrepancy search and its variations have been shown to achieve significant imp

ADecomposition-BasedImplementationofSearchStrategies

LAURENTMICHELandPASCALVANHENTENRYCK

BrownUniversity

Searchstrategies,thatis,strategiesthatdescribehowtoexploresearchtrees,haveraisedmuchinterestforconstraintsatisfactioninrecentyears.Inparticular,limiteddiscrepancysearchanditsvariationshavebeenshowntoachievesigni cantimprovementsinef ciencyoverdepth- rstsearchforsomeclassesofapplications.

Thisarticlereconsiderstheimplementationofdiscrepancysearch,andofsearchstrategiesingeneral,forapplicationswherethesearchprocedureisdynamic,randomized,and/orgeneratesglobalcuts(ornogoods)thatapplytotheremainingsearch.Itillustratesthatrecomputation-basedimplementationsofdiscrepancysearcharenotrobustwithrespecttotheseextensionsandrequirespecialcarewhichmayincreasethememoryrequirementssigni cantlyanddestroythegenericityoftheimplementation.

Toremedytheselimitations,thearticleproposesanovelimplementationschemebasedonprob-lemdecomposition,whichcombinestheef ciencyoftherecomputation-basedimplementationswiththerobustnessoftraditionaliterativeimplementations.Experimentalresultsonjob-shopschedul-ingproblemsillustratethepotentialofthisnewimplementationscheme,which,surprisingly,maysigni cantlyoutperformrecomputation-basedschemes.

CategoriesandSubjectDescriptors:D.3[Software]:ProgrammingLanguages;D.3.2

[ProgrammingLanguages]:LanguagesClassi cations—constraintandlogiclanguages;D.3.3

[ProgrammingLanguages]:LanguageConstructsandFeatures—constraints;controlstructuresGeneralTerms:Design,Languages

AdditionalKeyWordsandPhrases:Constraintprogramming,search,combinatorialoptimization

1.INTRODUCTION

Combinatorialoptimizationproblemsareubiquitousinmanypracticalapplica-tions,includingscheduling,resourceallocation,softwareveri cation,andcom-putationalbiologytonameonlyafew.Theseproblemsarecomputationallydif- cultingeneral(i.e.,theyareNP-hard)andtheirsolvingrequiresconsiderableThisresearchwassupportedinpartbyNationalScienceFoundation(NSF)AwardsDMI-0121495andACI-0121497.

Authors’presentaddresses:L.Michel,UniversityofConnecticut,ComputerScience&Engineering,191AuditoriumRoad,Storrs,CT06269;P.VanHentenryck,BrownUniversity,DepartmentofComputerScience,Box1910,Providence,RI02912;email:pvh@cs.brown.edu.

Permissiontomakedigitalorhardcopiesofpartorallofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforpro tordirectcommercialadvantageandthatcopiesshowthisnoticeonthe rstpageorinitialscreenofadisplayalongwiththefullcitation.CopyrightsforcomponentsofthisworkownedbyothersthanACMmustbehonored.Abstractingwithcreditispermitted.Tocopyotherwise,torepublish,topostonservers,toredistributetolists,ortouseanycomponentofthisworkinotherworksrequirespriorspeci cpermissionand/orafee.PermissionsmayberequestedfromPublicationsDept.,ACM,Inc.,1515Broadway,NewYork,NY10036USA,fax:+1(212)869-0481,orpermissions@. C2004ACM1529-3785/04/0400-0351$5.00

ACMTransactionsonComputationalLogic,Vol.5,No.2,April2004,Pages351–383.