Symmetries In CSP
Symmetries in CSPSymmetries in CSPElena ShermanUNL, CSEApril 18, 2009
Symmetries in CSPTable of contentsWhy Symmetry?Symmetry ExamplesApproaches for Symmetrical CSPsAdding symmetry-breaking global contraintsSearch space modificationHeuristics modificationHistorical Note
Symmetries in CSPWhy Symmetry?ContentsWhy Symmetry?Symmetry ExamplesApproaches for Symmetrical CSPsAdding symmetry-breaking global contraintsSearch space modificationHeuristics modificationHistorical Note
Symmetries in CSPWhy Symmetry?What is Symmetry?SymmetryIDefined as “patterned self-similarity”.IGenerated by a transformation S of an object O1 into O2 .IS(O1 ) is not distinguishable from O2 .ICommon S are translation, rotation and reflection.
Symmetries in CSPWhy Symmetry?Crafting a Paper SnowflakeHow to cut out a snowflake from a piece of paper?
Symmetries in CSPWhy Symmetry?Crafting a Paper SnowflakeHow to cut out a snowflake from a piece of paper?
Symmetries in CSPWhy Symmetry?Crafting a Paper SnowflakeHow to cut out a snowflake from a piece of paper?In general biological science problems have many geometric symmetries.
Symmetries in CSPWhy Symmetry?Why is Symmetry?ICSP (V , D, C ) NPC , but islands of tractability.IUsing the structure of CSP to reduce complexity, or to reduce theproblem size.ISymmetry can occur in V , D and C ex. All-Diff constraint.CSP’s elements that are symmetric under S create an equivalenceclass.IIProperty detected in one element of an equivalent class can begeneralized to all elements of that class. Ex.D {1, 2, 3, 4, 5, 6, 7} D {[2, 4, 6], [3, 5, 7]}.
Symmetries in CSPSymmetry ExamplesContentsWhy Symmetry?Symmetry ExamplesApproaches for Symmetrical CSPsAdding symmetry-breaking global contraintsSearch space modificationHeuristics modificationHistorical Note
Symmetries in CSPSymmetry Examples5-queens Symmetry Example S 180 Rotation
Symmetries in CSPSymmetry Examples5-queens Symmetry Example S 180 RotationIRotate by 180 degrees.
Symmetries in CSPSymmetry Examples5-queens Symmetry Example S 180 RotationIRotate by 180 degrees.
Symmetries in CSPSymmetry Examples5-queens Symmetry Example S 180 RotationIIIIRotate by 180 degrees.x1 exchanges with x5 and x2 with x4 .New domains θ(val) 6 val for each xi .Equivalence classes:IIVariables {x1 , x2 }, {x2 , x4 } and {x3 }.Values {1, 5}, {2, 4}, {3}.
Symmetries in CSPSymmetry Examples5-queens Symmetry Example S 180 RotationIIIIRotate by 180 degrees.x1 exchanges with x5 and x2 with x4 .New domains θ(val) 6 val for each xi .Equivalence classes:IIIVariables {x1 , x2 }, {x2 , x4 } and {x3 }.Values {1, 5}, {2, 4}, {3}.Reflection about the horizontal axis and vertical axis.
Symmetries in CSPSymmetry Examples5-queens Symmetry Example S 180 RotationIIIIRotate by 180 degrees.x1 exchanges with x5 and x2 with x4 .New domains θ(val) 6 val for each xi .Equivalence classes:IIIIVariables {x1 , x2 }, {x2 , x4 } and {x3 }.Values {1, 5}, {2, 4}, {3}.Reflection about the horizontal axis and vertical axis.Rotation by 360? Rotation by 90?
Symmetries in CSPSymmetry Examples5-queens - Different FormulationIX {x1 , x2 , x3 , x4 , x5 }ID {1, 2, . . . , 25}IWhat are the symmetries here? Do they include domains, variablesor both?
Symmetries in CSPSymmetry Examples5-queens - Different FormulationIX {x1 , x2 , x3 , x4 , x5 }ID {1, 2, . . . , 25}IWhat are the symmetries here? Do they include domains, variablesor both?
Symmetries in CSPSymmetry Examples5-queens - Different FormulationIX {x1 , x2 , x3 , x4 , x5 }ID {1, 2, . . . , 25}IWhat are the symmetries here? Do they include domains, variablesor both?
Symmetries in CSPSymmetry Examples5-queens - Different FormulationIX {x1 , x2 , x3 , x4 , x5 }ID {1, 2, . . . , 25}IWhat are the symmetries here? Do they include domains, variablesor both?
Symmetries in CSPSymmetry Examples5-queens - Different FormulationIX {x1 , x2 , x3 , x4 , x5 }ID {1, 2, . . . , 25}IWhat are the symmetries here? Do they include domains, variablesor both?
Symmetries in CSPSymmetry Examples5-queens - Different FormulationIX {x1 , x2 , x3 , x4 , x5 }ID {1, 2, . . . , 25}IWhat are the symmetries here? Do they include domains, variablesor both?IAll 8 symmetries.
Symmetries in CSPSymmetry ExamplesFormulation of CSP has Symmetry and not the ProblemIThe definition of the symmetry applies to the definition of CSP andnot to the problem itself.IDifferent CSP’s formulations of the same problem can have differentsymmetries.IWhat symmetry to select?
Symmetries in CSPSymmetry ExamplesFormulation of CSP has Symmetry and not the ProblemIThe definition of the symmetry applies to the definition of CSP andnot to the problem itself.IDifferent CSP’s formulations of the same problem can have differentsymmetries.IWhat symmetry to select? What about one that produces thesmallest number of equivalent classes?
Symmetries in CSPApproaches for Symmetrical CSPsContentsWhy Symmetry?Symmetry ExamplesApproaches for Symmetrical CSPsAdding symmetry-breaking global contraintsSearch space modificationHeuristics modificationHistorical Note
Symmetries in CSPApproaches for Symmetrical CSPsThree Approaches for Symmetrical CSPsAdding symmetry breaking global constraintsIAdding global constraints to convert it to an asymmetrical CSP.Modify searchIPruning symmetric states as they appear in search.Modify search heuristicsIUsing symmetry-breaking rules to guide search.
Symmetries in CSPApproaches for Symmetrical CSPsAdding symmetry-breaking global constraintsRemoving Symmetry from the Problem - Global SymmetryIPuget [93] while developing PECOS tool.ISymmetry can cause a combinatorial explosion of the search space.IArc-consistency AC is not adapted to symmetrical CSPs. Ex.Pigeon Hole problem.In symmetrical CSP a permutation of the variables map one solutiononto another solution.IIRemoving symmetrical solutions by adding a constraint - if C C 0then Sol(P 0 ) Sol(P) - reduction.IAdd static symmetry breaking constraints - an ordering constraintx1 x2 · · · xn - and do AC after that.
Symmetries in CSPApproaches for Symmetrical CSPsAdding symmetry-breaking global constraintsCreating a Global ConstraintExampleIV {v0 , v1 , v2 }, D {0, 1, 2}IC : v0 6 v1 v1 6 v2 v2 6 v0IHow many solutions?
Symmetries in CSPApproaches for Symmetrical CSPsAdding symmetry-breaking global constraintsCreating a Global ConstraintExampleIV {v0 , v1 , v2 }, D {0, 1, 2}IC : v0 6 v1 v1 6 v2 v2 6 v0IHow many solutions?Has a symmetry (permutation): v0 v1 , v1 v2 , v2 v0I
Symmetries in CSPApproaches for Symmetrical CSPsAdding symmetry-breaking global constraintsCreating a Global ConstraintExampleIV {v0 , v1 , v2 }, D {0, 1, 2}IC : v0 6 v1 v1 6 v2 v2 6 v0IIHow many solutions?Has a symmetry (permutation): v0 v1 , v1 v2 , v2 v0IAdding v0 v1 v2 - How many solutions?
Symmetries in CSPApproaches for Symmetrical CSPsAdding symmetry-breaking global constraintsGeneral DirectionIEnforcing GAC on this global constraint reduces the problem.IDepending on the decomposition of a problem GAC propagation canbe NPC .In ”other” constraint paper by Law at al. [CP07].IIIIProposed SigLex global constraint.Its GAC propagation is P.But it prunes only some symmetric values in general cases.
Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is Dynamic [Meseguer & Torras 2001]ISymmetries holding at the initial states is a global symmetry.
Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is Dynamic [Meseguer & Torras 2001]ISymmetries holding at the initial states is a global symmetry.
Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is Dynamic [Meseguer & Torras 2001]ISymmetries holding at the initial states is a global symmetry.
Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is Dynamic [Meseguer & Torras 2001]ISymmetries holding at the initial states is a global symmetry.
Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is Dynamic [Meseguer & Torras 2001]ISymmetries holding at the initial states is a global symmetry.IAfter an assignment to vi the global symmetry may break.
Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is Dynamic [Meseguer & Torras 2001]ISymmetries holding at the initial states is a global symmetry.IAfter an assignment to vi the global symmetry may break.
Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is Dynamic [Meseguer & Torras 2001]ISymmetries holding at the initial states is a global symmetry.IAfter an assignment to vi the global symmetry may break.
Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is Dynamic [Meseguer & Torras 2001]ISymmetries holding at the initial states is a global symmetry.IAfter an assignment to vi the global symmetry may break.IYet, new symmetries can appear in some states.
Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is DynamicISymmetries holding at the initial states is a global symmetry.IAfter an vi assignment the global symmetry can break.IYet, new symmetries can appear in some states.ISymmetries can be broken and restored during the search.
Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is DynamicISymmetries holding at the initial states is a global symmetry.IAfter an vi assignment the global symmetry can break.IYet, new symmetries can appear in some states.ISymmetries can be broken and restored during the search.
Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationPruning Symmetric States from SearchSymmetric Variables [Brown et al. 1989]IDoes not select vvp if vvp leads to a redundant partial assignment.IDetermines if a current partial assignment X is equivalent to asmaller assignment under a symmetry group G .IHas pseudo code of the Backtracking Algorithm with Symmetries.ISymmetries are given.
Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationPruning Symmetric States from SearchSymmetric Values [Freuder 1991]IOnly selects one val from equivalence class of values during vvpselection.IValues a and b are neighborhood interchangeable if each vvp isconsistent with their neighborhood.IAlgorithm to determine local value interchangeability is O(n2 d 2 ).ISymmetries are discovered.
Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetric Variables and Values [Backofen & Will CP99,Gent & Smith 2000]IDoes not interfere with the heuristic searches (variable ordering).IAdds symmetry breaking constraints to the right branches of searchtree.x1 2, x2 3 - backtracking
Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetric Variables and Values [Backofen & Will CP99,Gent & Smith 2000]IDoes not interfere with the heuristic searches (variable ordering).IAdds symmetry breaking constraints to the right branches of searchtree.x1 2, x2 3 - backtrackingx1 2, x2 6 3 - should we consider x4 3?
Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetric Variables and Values [Backofen & Will CP99,Gent & Smith 2000]IDoes not interfere with the heuristic searches (variable ordering).IAdds symmetry breaking constraints to the right branches of searchtree.x1 2, x2 3 - backtrackingx1 2, x2 6 3 - should we consider x4 3? Depends if x5 5 or notIf x5 6 5 then x2 3 and x3 3 are not equivalent. Generally it is not known ifx5 5 or x5 6 5.Adding a conditional constraint x1 1 x2 6 3 x5 5 x4 6 3.
Symmetries in CSPApproaches for Symmetrical CSPsHeuristics modificationUse Symmetry to Guide SearchDynamic Variable Ordering [Meseguer & Torras 2001]IIDirect search toward subspaces with many non-symmetric states.Selecting vvp that breaks the most of the symmetries.IIt will lead to more evenly distributed solutions in the CSP’s statespace.IMore about it in my project presentation.
Symmetries in CSPHistorical NoteContentsWhy Symmetry?Symmetry ExamplesApproaches for Symmetrical CSPsAdding symmetry-breaking global contraintsSearch space modificationHeuristics modificationHistorical Note
Symmetries in CSPHistorical NoteIAvoiding symmetric path in search [Glaischer 1874, Brown et al.1989]IValue interchangeability [Freuder 1991]ISymmetry breaking constraints [Puget 93, Backofen & Will 99]Discovering symmetriesIIIIEquivalent to graph isomorphism.Complexity unknown (P? NPC?)Discover symmetry generators with Nauty, Saucy, AUTOM
Symmetries in CSPHistorical NoteBibliography ICynthia A. Brown, Larry Finkelstein, and Paul Walton Purdom, Jr.Backtrack searching in the presence of symmetry.In AAECC-6: Proceedings of the 6th International Conference, onApplied Algebra, Algebraic Algorithms and Error-Correcting Codes,pages 99–110, London, UK, 1989. Springer-Verlag.Rolf Backofen and Sebastian Will.Excluding symmetries in constraint-based search.In CP ’99: Proceedings of the 5th International Conference onPrinciples and Practice of Constraint Programming, pages 73–87,London, UK, 1999. Springer-Verlag.Darga et al.Saucy.http://vlsicad.eecs.umich.edu/BK/SAUCY.
Symmetries in CSPHistorical NoteBibliography IIEugene C. Freuder.Eliminating interchangeable values in constraint satisfactionproblems.In In Proceedings of AAAI-91, pages 227–233, 1991.J.W.L. Glaisher.On the Problem of the Eight Queens.Philosophical Magazine, 48:457–467, 1874.Ian P. Gent and Barbara M. Smith.Symmetry breaking in constraint programming.In Proceedings of ECAI-2000, pages 599–603. IOS Press, 2000.Y. C. Law, J. H. M. Lee, Toby Walsh, and J. Y. K. Yip.Breaking symmetry of interchangeable variables and values.In Principles and Practice of Constraint Programming CP 2007,pages 423–437, London, UK, 2007. Springer-Verlag.
Symmetries in CSPHistorical NoteBibliography IIIBrendan .Pedro Meseguer and Carme Torras.Exploiting symmetries within constraint satisfaction search.Artif. Intell., 129(1-2):133–163, 2001.Jean-Francois Puget.On the satisfiability of symmetrical constrained satisfactionproblems.In ISMIS ’93: Proceedings of the 7th International Symposium onMethodologies for Intelligent Systems, pages 350–361, London, UK,1993. Springer-Verlag.Jean-Francois Puget.Automatic Detection of Variable and Value Symmetries, 2005.
Why Symmetry? Why is Symmetry? I CSP (V;D;C) 2NPC, but 9islands of tractability. I Using the structure of CSP to reduce complexity, or to reduce the problem size. I Symmetry can occur in V, D and C ex. All-Diff constraint. I CSP’s elements that are symmetric under Screate an equiva
3. Symmetries and Field Equations of the Bosonic String 26 3.1 Global Symmetries of the Bosonic String Theory Worldsheet 26 3.2 Local Symmetries of the Bosonic String Theory Worldsheet 30 3.3 Field Equations for the Polyakov Action 33 3.4 Solving the Field Equations 36 3.5 Exercises 42 4. Symmetries (Revisited) and Canonical Quantization 45
PID/SKU CSP-5216 CSP-5228 CSP-5436 CSP-5444 CSP-5456 Rack Size 1RU 2RU CPU Cores 16 28 36 44 56 On Board Processors 2 Redundant Power (110/220 VAC)
The symmetry of an isosceles triangle. Re ection (2 symmetries: Id, r) The symmetry of a tripod. Rotation (3 symmetries: Id, v, w) The symmetry of an equilateral triangle. (6 symmetries: Id, v,w, x,y,z) It is the action of transforming the gure that is referred to a
2. Introduction 2.1. Cloud Service Provider Instruction: Provide a one to two page high-level introduction to the Cloud Service Provider, including - The ownership of the CSP; - The locality of the CSP; - Where its cloud services are provided from; - Is there any potential extrajudicial control and interference over a CSP by a foreign entity;
Concentrating Solar Power (CSP) and biomass power plants, which is used as the basis to evaluate the technical and economic benefits associated with hybrid CSP-biomass energy systems. The paper initially analyses alternative configurations for a 10 MWe hybrid CSP- biomass combustion power plant.
Parametric Analysis of Particle CSP System Performance and Cost to Intrinsic Particle Properties and Operating Conditions Kevin J. Albrecht, Matthew L. Bauer, Clifford K. Ho ASME Energy and Sustainability July 16, 2019 Session 3-11: Integrated CSP Systems Two (ES2019-3893) SAND2019-8280C
from those treated by existing boiler and pressure vessel codes. This study is a gap analysis to identify differences between the safety regulation needs of emerging CSP technologies and existing ASME Boiler and Pressure Vessel codes (BPV). Six leading CSP technologies are examined. The safety
Grade 1 Mathematics Student At-Home Activity Packet This At-Home Activity Packet includes 16 sets of practice problems that align to important math concepts your student has worked with so far this year. We recommend that your student completes one page of practice problems each day. Encourage your student to do the best they can with this content—the most important thing is that they .
