L07: Symmetry Flashcards
What is symmetry?
- A structure preserving transformation
- A symmetry can be characterised as a bijection on assignments (1-1 mapping)
- Symmetry preserves solutionhood
How does symmetry partition complete assignments?
Symmetry partitions complete assignments into equivalence classes.
In each class, either none of the members are solutions, or all of them are.
Why do we want to recognise symmetry in constraints models?
We want to break symmetry in constraints to reduce the time taken to search for solutions.
What are the 2 types of symmetry?
Variable Symmetry
- Bijections can be characterised in terms of the variables alone
- Domain and codomain are the variables
- Swapping variables keeps the values intact
Value Symmetry
- Bijection can be characterised in terms of the values alone
- Domain and codomain are the values
- Swapping values keeps the variables intact
What is an example problem that has variable symmetry?
N-queens problem
What is an example problem that has value symmetry?
Map colouring problem
What are the consequences of a model containing symmetry?
There are fruitless searches in subtrees for which we have already searched the solutions in the same equivalence class.
Wastes time for searching (redundant)
How does symmetry arise?
Either- it is inherent in the problem, e.g. the n-queens problem has the symmetries of the square
Or- the symmetry is introduced in the modelling process. Knowing how symmetry is introduced during modelling can make symmetry detection and breaking easier
How can adding constraints affect symmetry?
- Disallow some of the elements of an equivalence class of assignments
- Considering order the elements to limit the different permutations of the solution
- If the problem is modelled properly, you will limit the solutions to one solution per equivalence class
- This can prune the search tree drastically
How do we formulate symmetry breaking constraints?
Define a canonical solution, and add constraints to choose it
We need:
- An ordering on variables
- An ordering on solutions
- Reformulate the problem so that it has a reduced amount of symmetry
- Add symmetry breaking constraints before the search starts, thereby making some symmetric solutions unacceptable while leaving at least 1 solution in each symmetric equivalence class.
- Break down symmetry dynamically during the search, adapting the search procedure appropriately.
What is lexicographic ordering?
Dictionary ordering of letters and numbers
Compare first characters, if they are the same, compare second characters
What is the aim of symmetry breaking?
Never explore 2 search states which are symmetric to each other, as we know that the result in both cases must be the same.
By recognising symmetry, we can exploit it to reduce the amount of search needed to solve the problem.
What is Lex-leader method?
- Choose an ordering on the variables
- Add one lexicographic ordering constraint per symmetry.
For each equivalence class of solutions under a symmetry group, we will predefine one to be the canonical solution. This is achieved by adding constraints before search starts which are satisfied by canonical solutions and not by any others.
We can induce an ordering on full assignments. Every permutation of assignments in the group gives us one <=lex constraint.
What are the pros and cons of the lex leader method?
Pro: breaks all symmetry
Con: Will require a large number of constraints
Compromise: use a subset of the lex-leader constraints
Many groups of solutions contain an exponential number of symmetries. Lex-leader requires a constraint for each element of the group which is not appropriate for all problems.
What is the Lex^2 method?
A significant fraction of lex-leader row/column symmetry can be represented by lex ordering the tows and columns.
Subset of lex-leader
