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

354 L.MichelandP.VanHentenryck

Section2introducestheabstractionsandnotationsusedthroughoutthearticletomeetthisgoal.Itde nesvariousconcepts,forexample,constraintstores,goals,con gurations,andcomputationpaths,andillustratesthemondepth- rstsearch.Section3brie yreviewsLDS,thesearchstrategyusedtoillustratetheimplementations.Section4describesthetraditionaliterativeimplementationofLDSandSection5presentstherecomputation-basedscheme.Section6introducesournovel,decomposition-based,implementationandSection7provesitscorrectness.Section8discusseshowtorepresentthequeueinrecomputation-basedanddecomposition-basedschemes.Section9generalizesthedecomposition-basedalgorithmtostrategiesspeci edbyevaluationandsuspensionfunctions.Section10presentstheexperimentalresultsandSection11concludesthearticle.Notealsothatthearticlecontainsthe rstdescriptionsoflimiteddiscrepancysearch,andsearchstrategiesingeneral,inanoptimizationsetting.

2.BACKGROUND

Thissectiondescribesthemainabstractionsandnotationsusedthroughoutthepapertosimplifythepresentation.Italsopresentsthehypothesesandprop-ertiesusedinthealgorithms.Ourgoalistopresentthealgorithmsatahighlevelofabstractionwhilegivingenoughdetailtocapturetheirtimeandspacerequirementsandtodiscusstheirrobustness.Asaconsequence,thepresen-tationofthealgorithmsrequiresomemachinerythatwouldnotbenecessaryotherwise.Ontheonehand,recursionisnotusedtosaveandrestoreconstraintstores,sincethiswouldhidethememoryandtimerequirementsofthealgo-rithmsandtherobustnessissues.Ontheotherhand,searchproceduresarenotassumedtobedescribedbystaticsearchtrees,sincethedynamicnatureofsearchproceduresistheprimarydif cultyindesigningef cientimplementa-tionsoflimiteddiscrepancysearchandofsearchstrategiesingeneral.Instead,thealgorithmsuseadynamicbranchingfunctionwhichconstructsthesearchtreedynamically.

Ournotationsandabstractionsareessentiallyborrowedfromconstraintlogicprogrammingbutaresimplerbecauseofthenatureofconstraintsatisfac-tionproblems.Section2.1describesconstraintstoresandtheiroperations,Sec-tion2.2de nestheconceptofsolutionsandoptimalsolutions,Section2.3showshowsearchproceduresareexpressedandSection2.4speci estheirrequiredproperties.Section2.5illustratesthenotationsandabstractionsbyshowinghowtoimplementdepth- rstsearch.Section2.6discussescomputationpathsthatarefundamentalinimplementationsofLDS.

2.1ConstraintStores

Aconstraintstoreisa nitesequence c1,...,cn ofconstraints(orconjunctionofconstraints).Constraintstoresaredenotedbytheletterσ,possiblysubscriptedorsuperscripted.Constraints,orconjunctionsofconstraints,aredenotedbytheletterc,possiblysubscriptedorsuperscripted.Givenaconstraintstoreσ= c1,...,cn ,weuseσ∧ctodenotec1∧···∧cn∧c.Ouralgorithmsuse vemainoperationsonconstraintstoreswhicharespec-i edinFigure1.FunctionSUCCESS(σ)returnstrueifσisasolution,thatis,σACMTransactionsonComputationalLogic,Vol.5,No.2,April2004.