A Decomposition-Based Implementation of Search Strategies(2)

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

352 L.MichelandP.VanHentenryck

expertiseinoptimizationandsoftwareengineering,aswellasintheapplicationdomain.

Theconstraintsatisfactionapproachtocombinatorialoptimization,whichemergedfromresearchinarti cialintelligence(e.g.,Fikes[1968],Lauriere

[1978],Mackworth[1977],Montanari[1974],andWaltz[1972])andprogram-minglanguages(e.g.,Colmerauer[1990],VanHentenryck[1989],andJaffarandLassez[1987]),consistsofatreesearchalgorithmusingconstraintstoprunethesearchspaceateverynode.Solvingaprobleminthisapproachamountstospecifyingasetofconstraintsdescribingthesolutionsetandasearchprocedureindicatinghowtosearchforsolutions.Constraintprogram-ming(e.g.,Colmerauer[1990],JaffarandLassez[1987],andVanHentenryck

[1989])aimsatsimplifyingthistaskbysupportingrichlanguagestospecifyconstraintsandsearchprocedures.

Thesearchprocedureinconstraintsatisfactionimplicitlydescribesthesearchtreetoexplore.Itdoesnotspecifyhowtoexploreit,whichistheroleofsearchstrategies.Traditionally,thesearchtreeisexploredusingdepth- rstsearch.However,inrecentyears,novelsearchstrategies(e.g.,HarveyandGinsberg[1995],Korf[1996],Meseguer[1997],andWalsh[1997])haveraisedmuchinterest.Inparticular,limiteddiscrepancysearch(LDS)anditsvaria-tionshavebeenshowntoachievesigni cantimprovementsinef ciencyoverdepth- rstsearchforsomeclassesofapplications.Thebasicideaunderlyingdiscrepancysearchistoexplorethesearchspaceinwavesorganizedaccordingtoagoodheuristic.The rstwave(wave0)simplyfollowstheheuristic.Waveiexploresthesolutionswhichcanbereachedbyassumingthattheheuristicmadeimistakes.

Becauseoftheirsuccessonavarietyofpracticalproblems(e.g.,HarveyandGinsberg[1995],LaburtheandCaseau[1998],andPerron[1999]),searchstrategiesbecameanintegralpartofconstraintprogramminglanguagesinre-centyears(e.g.,LaburtheandCaseau[1998],Perron[1999],Schulte[1997],andVanHentenrycketal.[2000]).Inparticular,theOZprogrammingsystempioneeredthespeci cationofgenericsearchstrategiesthatcanbespeci edin-dependentlyofsearchprocedures[Schulte1997].Asaconsequence,asearchstrategycanbeappliedtomanysearchproceduresandasearchprocedurecanbe“explored”putationstatesare,ingeneral,demandinginmemoryrequirementsbuttheyhavemanyappeallinguses(e.g.,Schulte

[2000]).ThesearchlanguageSALSA[LaburtheandCaseau1998]alsocontainsanumberofprede nedgenericsearchstrategies.Morerecently,itwasshowninPerron[1999]thatmanysearchstrategiescanbespeci edbytwofunctionsonly:anevaluationfunctionwhichassociatesavaluewitheverynodeinthesearchtreeandasuspensionfunctionwhichindirectlyspeci eswhichnodetoexpandonnext.TheimplementationtechnologyinPerron[1999]isofpartic-ularinterest.WhenappliedtoLDS,itfeaturesarecomputation-basedschemeinsteadofthetraditionaliterativeexplorationinitiallyproposedinHarveyandGinsberg[1995].Moreprecisely,theimplementationisorganizedaroundaqueuewhichstoresnodestoexploreandusesbacktrackingandrecomputationtorestorethenodepoppedfromthequeue.NodesinthequeuearerepresentedACMTransactionsonComputationalLogic,Vol.5,No.2,April2004.