Tractable symmetry breaking for CSPs with interchangeable values

Symmetry breaking in CSPs has attracted considerable attention in recent years. Various general schemes have been proposed to eliminate symmetries during search. In general, these schemes may take exponential space or time to eliminate all symmetries. This

TractableSymmetryBreakingforCSPswithInterchangeableValues

P.VanHentenryck

DepartmentofComputerScienceBrownUniversity,Box1910Providence,RI02912

Abstract

SymmetrybreakinginCSPshasattractedconsid-erableattentioninrecentyears.Variousgeneralschemeshavebeenproposedtoeliminatesym-metriesduringsearch.Ingeneral,theseschemesmaytakeexponentialspaceortimetoeliminateallsymmetries.ThispaperstudiesclassesofCSPsforwhichsymmetrybreakingistractable.Itidenti esseveralCSPclasseswhichfeaturevar-iousformsofvalueinterchangeabilityandshowsthatsymmetrybreakingcanbeperformedincon-stanttimeandspaceduringsearchusingdedicatedsearchprocedures.Experimentalresultsalsoshowthebene tsofsymmetrybreakingontheseCSPs,whichencompassmanypracticalapplications.

1Introduction

Symmetrybreakingforconstraintsatisfactionproblemshasattractedconsiderableattentioninrecentyears(SeethelastCPproceedings,theCP’01andCP’02workshopsonsym-metries,and[Crawfordetal.,1996;Freuder,1991;BackofenandWill,1999;Puget,1993]forsomelessrecentpapers).Indeed,manyapplicationsnaturallyexhibitsymmetriesandsymmetrybreakingmaydrasticallyimproveperformance(e.g.,[Barnier]andBrisset,2002;MeseguerandTorras,2001;Puget,2002).AnimportantcontributioninthisareahasbeenthedevelopmentofvariousgeneralschemesforsymmetrybreakinginCSPs(e.g.,SBDS[GentandSmith,2000]andSBDD[Fahleetal.,2001;FocacciandMilano,2001]).Un-fortunately,theseschemes,ingeneral,mayrequireexponen-tialresourcestobreakallsymmetries.Indeed,someschemesrequireexponentialspacetostoreallthenogoodsgeneratedthroughsymmetries,whileothersmaytakeexponentialtimetodiscoverwhetherapartialassignmentissymmetrictooneoftheexistingnogoods.Asaconsequence,practicalapplica-tionsoftenplacelimitsonhowmanynogoodscanbestoredand/orwhichsymmetriestobreak.

Thispaperapproachessymmetrybreakingfromadiffer-ent,orthogonal,standpoint.ItsgoalistoidentifyclassesofCSPsthatarepracticallyrelevantandforwhichsymmetrybreakingistractable,i.e.,symmetrybreakingispolynomialintimeandspace.Itidenti esseveralsuchclasses,which

P.Flener,J.Pearson,andM.Agren

DepartmentofInformationTechnology

UppsalaUniversity,Box337S-75105Uppsala,Sweden

encompassmanypracticalapplications.TheseCSPsfea-turevariousformsofvalueinterchangeabilityandthepapershowsthatsymmetrybreakingcanbeperformedinconstanttimeandspaceduringsearchusingdedicatedsearchproce-dures.Thepaperalsoreportspreliminaryexperimentalre-sultsindicatingthatsymmetrybreakingontheseCSPsbringssigni cantcomputationalbene ts.Finally,thepaperintro-ducesthenewnotionsofexistentialandabstractnogoods,whichwereusedtoderivetheresultsforthevariousCSPclasses.Webelievethatthesenotionsarehelpfultoderivemanyotherclassesoftractablesymmetries.Inparticular,theyalsoallowedustoderiveclassesoftractablevariablesymmetries,whichwecannotincludehereforspacereasons.Assuch,thispapershouldbeviewedonlyasa rststepinthisfascinatingarea.

Itisalsousefultocontrastourapproach]withtheresearchavenuepioneeredby[Freuder,1991onvalueinterchange-ability.Freuderalsointroducedvariousformsofvalueinter-changeability.However,hisgoalwastodiscoversymmetriesinsideCSPsandtoreformulatethembypreprocessingtore-movesymmetries.Unfortunately,discoveringsymmetriesinCSPsisnottractableformanyinterestingclassesofCSPs.Ourresearch,incontrast,assumesthatmodellersareawareofthesymmetriesintheirapplications.Itfocusesonhowtoexploitthisknowledgeduringsearchtoeliminatesymmetriesef ciently.Consider,forinstance,thescene-shootingprob-lemfeaturedin[VanHentenryck,2002].Thisproblemaimsatproducingamovie(oraseries)atminimalcostbydecid-ingwhentoshootscenes.Eachsceneinvolvesanumberofactorsandatmost5scenesadaycanbe lmed.Allactorsofascenemustbepresentonthedaythesceneisshot.Theac-torshavefeesrepresentingtheamounttobepaidperdaytheyspendinthestudio.Thegoaloftheapplicationistominimizetheproductioncosts.Anoptimalsolutiontothisproblemcanbemodelledasanassignmentofscenestodayswhichmin-imizestheproductioncosts.Itshouldbeapparentthattheexactdaysassignedtothesceneshavenoimportanceinthisapplicationandarefullyinterchangeable.Whatisimportantishowthescenesareclusteredtogether.Ourapproachdoesnotaimatdiscoveringthisfact;ratheritfocusesonhowtoexploitittoeliminatethesymmetriesitinduces.

Therestofthepaperisorganizedasfollows.Aftersomepreliminaries,Sections3,4,and5studythreeclassesofCSPsforwhichsymmetrybreakingistractable.Forspacereasons,

Symmetry breaking in CSPs has attracted considerable attention in recent years. Various general schemes have been proposed to eliminate symmetries during search. In general, these schemes may take exponential space or time to eliminate all symmetries. This

onlythe rstclassispresentedinfulldetailwithproofs.Sec-tion6brie yreportssomeexperimentalresults.Section7concludesthepaper.

2Preliminaries

Thissectionde nesthemainconceptsusedinthispaper.Thede nitions,althoughtheycapturetheinformalmeaningofCSPs,arenon-standardandsimplifythede nitionsandproofsconsiderably.Thebasicideaisthatthesetofcon-straintsisabstractedbyaBooleanfunctionwhichholdsifalltheconstraintsaresatis ed(sincewearenotinterestedintheconstraintstructure).Solutionsarealsorepresentedasfunc-tions(assignments)fromvariablestotheirsetsofvalues.De nition2.1.ACSPisatriplet,wheredenotesthesetofvariables,denotesthesetofpossiblevaluesfor

thesevariables,and

isaconstraintthatspeci eswhichassignmentsofvaluestothevariablesaresolutions.ACSPisdenotedsuchsolutionthattoaCSPby

..Thesetofsolutionsisafunction

toa

AlgorithmstosolveCSPsmanipulatepartialassignments.It

isoftenimportanttoreasonaboutwhichvariablesarealreadyassigned(thedomainofthepartialassignment)andthesetofvaluestheyareassignedto(theimageoftheassignment).Notethatdomainsrepresentsetsofvariablesinthispaper(notvaluesasistraditional),sinceweusefunctionstomodel(partial)assignments.

De nition2.2.LetbeaCSP.Apartialas-signmentforisafunction.Thedo-mainof,denotedby,is.Theimageof,de-notedby,isthesetForeachvalue,weuse.

todenotetheset

Inthispaper,weoftendenoteapartialassignmentbya

conjunctionofequations

whereassignment.Forinstance,functionwhosedomainis

valueandwhichrepresentsthepartialassignsthe

theto.Wealsodenotetheemptyassignmentby.Thenextfourde nitionsde nenogoodsformallyandwhena(partial)assignmentviolatesanogood.

De nition2.3.LetbeaCSPandbeapartialassignmentfor.Apartialassignmentand

isanextensionofforif

De nition2.4.LetbeaCSPandbeapartialassignmentfor.forisdenotedbyforAcompletion.Theofforisanex-tensionof.

setofallcompletionsofDe nition2.5.LetbeaCSP.Anogoodfor

isapartial

assignmentforsuchthat

.

De nition2.6.LetbeaCSP,beanogoodfor,and

beapartialassignmentfor.violatesnogoodforifisanextensionoffor.

Proposition,then2.7.LetbeaCSP.If.

violatesnogoodfor

Thislastpropositionshowsthatnogoodscanbeliftedfromthechildrentotheirparent.Proposition2.8..LetLetbebeaCSPand

beanogoodandapartialassignmentforwith

forlet.Thenevery

isanogoodfor.

3Value-InterchangeableCSPs

Therearemanyapplicationsinresourceallocationandschedulingwheretheexactvaluestakenbythevariablesarenotimportant.Whatissigni cantiswhichvariablestakethesamevaluesor,inotherterms,howthevariablesareclus-tered.Thisnotionofsymmetryiswhat[Freuder,1991]callsfullinterchangeabilityforallvariablesandallvalues.Theprototypicalexampleisgraph-coloring.Another,morecom-plex,exampleisthesceneallocationapplicationmentionedintheintroduction.Thissectionshowsthatsymmetrybreak-ingfortheseproblemsistractableandtakesconstanttimeandspace.We rstde nevalue-interchangeableCSPs.De nition3.1.LetbeaCSP.isvalue-interchangeableif,foreachsolutionandeachbijection,thefunction.

Inthefollowing,weuseICSPasanabbreviationforvalue-interchangeableCSP.ThefollowingtheoremisafundamentalcharacterizationofnogoodsforICSPs.Theorem3.2.LetbeanICSP,letbea

nogoodfor,andlet

beabijection.Thenisanogood.

TheclosureofanogoodforanICSPcapturesallthe“sym-metric”nogoodsthatcanbeobtainedfrom.De nition3.3.LetbeanICSPandbeanogoodfor,isthe.setTheclosureofforis,adenotedbijection

by

Wenowshowthattheclosureofanogoodcanbecharac-terizedcompactlyandthatmembershiptotheclosureofanogoodcanbetestedinlineartimeforICSPs.We rstintro-ducetheconceptofexistentialnogood,whichsimpli estheproofsandintuitions.De nition3.4.LetbeanICSPandbeanogoodfor.Lettialnogoodoffor,denotedby.The,isexisten-thesetofallfunctionssatisfying

Thefollowinglemmaindicatesthatanexistentialnogoodpre-ciselycapturestheclosureofanogood.

Lemma3.5.LetbeanISCPandbeanogoodfor.

Then

.Proof.Let

image,wehavethat

.Byde nitionofthe

Symmetry breaking in CSPs has attracted considerable attention in recent years. Various general schemes have been proposed to eliminate symmetries during search. In general, these schemes may take exponential space or time to eliminate all symmetries. This

We rstshowthat

..suchthat

.ThisThus,meanssatis es

thatthereexistsabijectionLet

byde nitionofabijection,andhence.Wenowshowthat

.Let

suchthat

.Thereexistsomevalues

Sincearealldifferent,theresatisfying

and

.

Henceexistscanbearewrittenbijection

asItisnotobviousthatmembershiptoanexistentialnogoodcanbetestedef ciently,sinceitinvolvesanexistentialquanti ca-tion.However,duetothenatureoftheunderlyingconstraints,itiseasytoeliminatetheexistentialvariablesbyselectingarepresentativeforeachsettivationunderlyingtheconceptof.abstractThisispreciselynogoodsthede nedmo-below.Considertheexistentialformula

Thevariables

,

,and

canbeeliminatedtoproduce

De nition3.6.LetbeanICSPand

bea

nogoodfor.Let

andlet

Theabstractnogoodofwrt,denotedby

,

isthesetoffunctions

satisfying

Lemma3.7.LetbeanICSPandbeanogoodfor.Then.

Forsimplicity,wewilloftendenotetheabstractnogoodcon-ditionintermsofglobalconstraints

whereholdsifallthearethesame

value.Itcanbeseenthatthereexistsalineartimealgorithmtotestwhether.aItpartialsuf cesassignmenttoviolatesanogoodin

mulaabovewhenevertestwhether.

satis esthefor-Lemma3.8.LetbeanICSP,beanogoodfor,andbeapartialassignment.Thereexistsalinear-timealgorithmthattestswhetherviolatesanynogoodinP.

Proof.Directconsequenceoflemmas3.5and3.7andthefact

thattheabstractnogoodislinearin

.Lemma3.9.,Let

and

bebeanogood.abeanICSP,

forLetpartialevery

assignmentforwith.Then,

1.isanogoodfor;2.ifviolatesanogoodinviolatesanogoodinP.

P,thenLemmas3.8and3.9indicatethatsymmetrybreakingistractableforICSPs.Lemma3.9indicatesthatabstractno-goodsareneededonlyforfrontiernodesofthesearchtree(i.e.,closednodeswhoseparentsareopen).Onceitschildrenareexplored,theabstractnogoodoftheparentsubsumestheabstractnogoodsofitschildren.Hence,maintainingtheno-goodtakesspace

ifisthesetoffrontiernodes.Weformalizethisresultusingvariabledecompositiontrees.De nition3.10.Avariabledecompositionwherenodesrepresent,wherepartialassignmentsfor,treeisasearchforaCSP

andnodestree

aredecomposedasfollows:givenanoderepresentingtialassignment,where

drenrepresent,itsachil-par-forthesomepartialvariableassignments

.

Notethatvariabledecompositiontreescapturebothstaticanddynamicvariableorderings.Theorem3.11.LetbeanICSPandletbethesetoffrontiernodesinavariabledecompositionsearchtreefor.Symmetrybreakingforrequiresspaceforstor-ingthenogoods.Inaddition,testingifapartialassignmentviolatesanogoodtakestimeintheworstcase.Theresultabovecanbestrengthenedconsiderablyinfact.Wewillshowthatsearchproceduresexploringavariablede-compositiontreecanremoveallsymmetriesinconstanttimeandspace.Beforepresentingthetheoreticalresults,weillus-tratetheintuitionusingdepth- rstsearch.Thebasicintuitioncomesfromthestructureoftheabstractnogoods.Considerthepartialassignment

andassumethatdepth- rstsearchtriestoassignvariable

andthatproducesthesetofanpossibleabstractnogoodvaluesiswhich.holdsThefailureif

of

allequal(

allequal()alldiff()Sinceremaininstantiatedwhenthenextvalueistriedfor,theabstractnogoodforthispartofthisnextbranchholdsifTheassignments

imposingthatbeassigneda

valuedifferentfrom.producesimilarabstractnogoods.Nowobserveandwhathap-pensforanassignmentofavalue,say6.Theab-stractnogoodisnowde nedas

allequal(

allequal()alldiff())

whichcanbepartiallyevaluatedtoalldiff(disjunctionofallthesenogoodscanbepartiallyevaluated).Theto

Symmetry breaking in CSPs has attracted considerable attention in recent years. Various general schemes have been proposed to eliminate symmetries during search. In general, these schemes may take exponential space or time to eliminate all symmetries. This

boolILABEL()returnILABELA(,);boolILABELA()

ifthenreturn;selectif

:=in;

;thenselectin;:=;

forall()

:=;

if

ifILABELA(then)then

returntrue;

returnfalse;

Figure1:ALabelingProcedureforICSPs.

alldiff(

)

whichcannotbesatis edbyanyassignmentto.Itfol-lowsthatmustonlybeassignedtothepreviouslyassignedvaluesortoexactlyonenewvaluein.Inotherwords,inavariabledecompositiontree,onlysomeofthechildrenneedtobeexplored:thosewhichassignvariable

toavalueinandexactlyoneotherchild.Notethatthisresultisindependentfromthesetofconstraints.Itistheessenceofthelabelingprocedureforgraph-coloringin[Kubaleand[Jackowski,1985]andinthesceneallocationprobleminVanHentenryck,2002].Thisprocedure,whichbreaksallsymmetriesforICSPs,isformalizedinFigure1.Itusesthefunction()whichsatis estheproperty

Toourknowledge,thispaperprovidesthe rstformalproofthatthesealgorithmsbreakallthesymmetriesintheirrespec-tiveproblems.ToprovethecorrectnessofILABEL,andotherrelatedsearchprocedures,itisusefultointroducetheconceptofcompactvariabledecompositiontree.

De nition3.12.Acompactvariabledecompositiontreefor

anICSP

,whereasearchrepresentingandnodestreewhereaaredecomposednodesrepresent,isasfollows:partialassignmentsgivenafortherearechildren,partialforrepresentingsomeassignmentnodevariable,where

thepartialassignments

,

forallrepresentingapartialassignmentandexactlyonechild

ifisnotempty.

forsome,Thefollowinglemma,whichstatesthatcompactvariablede-compositiontreesarecomplete,followsdirectlyfromtheex-aminationofthenogoodsabove.

Lemma3.13.Let

beanICSPandbeallthecompleteassignmentsinavariabledecompositiontreeforisa.bijectionThen,theisclosureequalto.

Ournextlemmastatesthatacompactvariabledecompositiontreenevermatchesanynogoodgeneratedduringsearch.

Lemma3.14.LetbeanICSPandbeacompactvari-abledecompositiontreefor.Thepartialassignmentofanodeinnevermatchesanynogoodgeneratedduringtheexplorationof(excepttheoneitpossiblygenerates).

Proof.ByLemma3.9,itsuf cestoshowthatapartialassign-mentnevermatchesanogoodgeneratedbyitssiblingsor

thesiblingsofoneofitsancestorsinthetree.Theproofisbyinductiononthedepthofthetree.Atthedepthof,theresultfollowsfromtheinspectionsofthenogoodasdiscussedear-lier.Consideradepthoneoftheleftorrightbranchesandatthatanogooddepth.Wegeneratedcanrestrictbyattentiontotheprojectionoftothevariablesinstantiatedatthatdepth,i.e.,wecanrestrictattentiontosatisfying

Weshowthatassignedatdepth.Observethatthere.existsLetabepartialthevariableassign-mentsuchthatforsome

andand,

.Byde nitionofacompactvariabledecompositiontree,thevaluesandmustbelongtoConsiderthecase,where

where.

thatthereexist.Thatmeansbijection.Hence

,itandandinsuchthat

canberewrittenas.IfAssumenowthat,whichlowsthatandisimpossible.forsome

somebijection..Hence

Ifforsome.Itfol-,thenandthat

Assumethatwhichisimpossible.for

Ifandand.Then,

Hence,

,thenforsomefor.

sinceforsome,whichsome.

isbijectionimpossible.

ThecorrectnessofProcedureILABELfollowsfromthetwolemmasabove.Othersearchstrategies,e.g.,LDS,alsore-moveallsymmetriesinconstanttimeandspace.

Theorem3.15.ProcedureILABELbreaksallthesymme-triesinconstanttimeandconstantspaceforanICSP,i.e.,itnevermatchesanymemberoftheclosureofanynogoodgeneratedduringsearch.

4Piecewise-InterchangeableCSPs

Inmanyapplications,e.g.,inresourceallocationandschedul-ing,thevaluesaretakenfromdisjointsetsbuttheyarein-terchangeableineachset.Forinstance,inthescenealloca-tionproblem,wecaneasilyimagineaversionoftheproblemwheredaysaredividedinmorningandafternoonsessions.Actorsprobablyhavestrongpreferences(andthusdifferentfeesforthemorningandafternoonsessions)butthedayofthesessionmaynotmatter.Thispapercapturesthis(morelim-ited)formofinterchangeabilitybypiecewiseinterchangeableCSPs.We rstde nethisclassofCSPsformallyandthende-rivesimilarresultsasforICSPs.Westatethemainde nitionsandtheoremsonly,sincethederivationissimilartotheoneforICSPs.Astraditional,weusetodenotethedis-jointunionof

and.Ourde nitionsandresultsonly

Symmetry breaking in CSPs has attracted considerable attention in recent years. Various general schemes have been proposed to eliminate symmetries during search. In general, these schemes may take exponential space or time to eliminate all symmetries. This

considertwodistinctsetsofvalues,forsimplicity.Itiseasytogeneralizethemtoanarbitrarynumberofsets.De nition4.1.Letandbetwodisjointsets.Apiece-wisebijectionisabijectionde ned

as

.

ifwhereisabijectionDe nition4.2.Letpiecewisevalue-interchangeableif,foreachbeaCSP.is,theandfunctioneachpiecewisebijectionsolution

.

Inthefollowing,weusePICSPasanabbreviationforpiece-wisevalue-interchangeableCSP.De nitionbeanogood4.3.LetbeaPICSPandisapiecewise,foris.Theclosureoffor,denotedby

bijection

theset

WenowspecifytheabstractnogoodsforPICSPs.Thekeyintuitionistoseparatethevaluesfromand.De nition4.4.LetPICSPand

beanogood,wherefor.Letbea

,andlet

Theabstractnogoodofwrt,denotedby

,

isthesetoffunctions

satisfying

Figure2depictsalabelingprocedurePILABELforPICSPs,

whichbreaksallvaluesymmetriesinconstanttimeandspace.ProcedurePILABELgeneralizesILABELbyconsideringthealreadyassignedvaluesinbothsetsand,aswellasonenewvalue(ifany)frombothsets.

Theorem4.5.ProcedurePILABELbreaksallthesymme-triesinconstanttimeandconstantspaceforPICSPs.

5Wreath-ValueInterchangeableCSPs

Wenowconsideranother,morecomplex,classofCSPs,whichassignsapairofvaluestoeachvariable.Valuesinarefullyfrominterchangeableasetand,fora xedvaluein,thevaluesinarefullyinter-changeableaswell.Theseproblemsarecalledwreathvalue-interchangeableinthispaper,becausethesymmetrygroupcorresponds]toawreathproductofsymmetrygroups[Camer-son,1999.Suchproblemsarisenaturallyinavarietyofap-plicationsinresourceallocationandscheduling.Consider,forinstance,theproblemofschedulingameetingwheredif-ferentgroupsmustmeetsomedayoftheweekinsomeroomsubjecttoconstraints.Thedaysarefullyinterchangeableand,onagivenday,theroomsarefullyinterchangeable.Sym-metrybreakingforawreathvalue-interchangeableCSPistractable.

boolPILABEL()returnPILABELA(,);

boolPILABELA(ifthenreturn)

;selectin;

:=;:=;

if

thenselectinifthen

;:=;selectinforall(

);:=;

:=;ififPILABELA(then

)then

returntrue;

returnfalse;

Figure2:ALabelingProcedureforPICSPs.

De nition5.1.Letand

betwosets.Awreathbijec-tion

isabijectionde nedas

whereisabijectionand()isabijection.

De nition5.2.Let

iswreathvalue-interchangeableif,foreachbeaCSP.thefunction

andeachwreathbijectionsolution

,

.Inthefollowing,weuseWICSPasanabbreviationforwreathvalue-interchangeableCSP.Wealsousethefollowingnota-tions.isaIfsetoftuples,isdenotesthedenotesapair,setthesetandand

.Ifisanassignment,

If

denotestheset.

De nitionbeanogood5.3.forLet

.Theclosureofforbea,WICSPdenotedandisawreathbijection

,istheset

by

WenowspecifyabstractnogoodsforWICSPs.

De nitionbeanogood5.4.forLet

.LetbeaWICSP,andlet

,andlet

Theabstractnogoodofwrt,denotedby

,

isthesetoffunctions

satisfying

Symmetry breaking in CSPs has attracted considerable attention in recent years. Various general schemes have been proposed to eliminate symmetries during search. In general, these schemes may take exponential space or time to eliminate all symmetries. This

boolWILABEL()returnWILABELA(,);boolWILABELA(ifthenreturn)

;selectin;

:=;

if

thenselectin;:=forall()

;:=if

then;

selectin;:=forall()

;:=if

;

ifWILABELA(then)then

returntrue;

returnfalse;

Figure3:ALabelingProcedureforWICSPs.

Theorem5.5.ProcedureWILABELbreaksallthesymme-triesinconstanttimeandconstantspaceforaWICSP.

6ExperimentalResults

Thissectiongivessomepreliminaryresultsshowingtheben-e tsofsymmetrybreakingontheseclassesofproblems.Ta-ble1givesresultsongraphcoloring,anICSP,andonparti-tionedgraphcoloring,aPICSP.Inpartitionedgraphcoloring,thecolorsaredividedin4groupsandarefullyinterchange-ableineachgroup.Theconstraintsexpresstheusualgraph-coloringproperty:notwoadjacentverticesarecoloredwiththesamecolor.Table1givestheresultofcoloringgraphswith50%edgedensitywithatmost

7040.3172960.2674340.6076240.2578260.8780860.2282460.6783420.30

Table1:plexstructure(e.g.,aCartesianproduct).Therearesev-eralclassesofsuchCSPsforwhichsymmetrybreakingistractable,althoughmorecomplex.FindingeffectivesearchproceduresfortheseCSPsisalsoachallengingproblem.

8Acknowldegments

Specialthankstothereviewersfortheirveryinterestingcom-ments.AllauthorsarepartlysupportedbyaSTINTinsti-tutionalgrantIG2001-67ofSTINT.P.VanHentenryckispartlysupportedbyanNSFITRAwardDMI-0121495.TheSweden-basedauthorsarealsosupportedbygrant221-99-369oftheSwedishResearchCouncil.

References

[BackofenandWill,1999]RolfBackofenandSebastianWill.Ex-cludingsymmetriesinconstraint-basedsearch.InCP’99.

[BarnierandBrisset,2002]N.BarnierandP.Brisset.SolvingtheKirkman’sschoolgirlprobleminafewseconds.InCP’2002.[Camerson,1999]P.Cameron.PermutationGroups,CambridgeUniv.Press,1999.

[Crawfordetal.,1996]J.Crawfordetal.Symmetrybreakingpred-icatesforsearchproblems.InKR’96.

[Fahleetal.,2001]SchambergerFahle,Torsten,Stefan,andMeinolfSellmann.Symmetrybreaking.InCP’2001.

[FocacciandMilano,2001]FilippoFocacciandMichaelaMilano.Globalcutframeworkforremovingsymmetries.InCP’2001.[Freuder,1991]E.Freuder.Eliminatinginterchangeablevaluesinconstraintsatisfactionproblems.InProc.AAAI’91.

[GentandSmith,2000]IanP.GentandB.Smith.Symmetrybreak-ingduringsearchinconstraintprogramming.InECAI’2000.[KubaleandJackowski,1985]M.KubaleandD.Jackowski.AGeneralizedImplicitEnumerationAlgorithmforGraphColor-ing.CACM,28(4):412–418,1985.

[MeseguerandTorras,2001]P.MeseguerandC.Torras.Exploit-ingsymmetrieswithinconstraintsatisfactionsearch.Arti cialIntelligence,129(1-2):133–163,2001.

[Puget,1993]J.-F.Puget.Onthesatis abilityofsymmetricalcon-strainedsatisfactionproblems.InISMIS’93.

[Puget,2002]J.-F.Puget.SymmetryBreakingRevisited.InCP’2002.

[VanHentenryck,2002]rmsJournalonComputing,14(4):345–372,2002.

本文来源：https://www.bwwdw.com/article/lxe1.html