New Developments in Symmetry Breaking in Search Using Computational Group Theory - Artificial Intelligence and Symbolic Computation - page 204

symmetric groups, it is relatively straightforward to develop tractable algorithms
for constructing GE-trees. However at present we have no algorithm for arbitrary
groups: the diculty is that the action of the variable group does not, in general,
map nodes of a search tree to nodes of a search tree. Therefore to solve this
problem in general, we seek to develop hybrid approaches between our GE-tree
construction and pre-existing symmetry breaking algorithms.

2 Symmetry Breaking by Dominance Detection

In this section we briefly describe symmetry breaking by dominance detection
(SBDD). Let L be any CSP with symmetry group G . During backtrack search
we maintain a record of fail sets corresponding to the roots of completed

subtrees. Each fail set consists of those ( var = val ) assignments made during
search to reach the root of the subtree. We also keep track of the set P of current
ground variables: variables having unit domain, either by search decision or by
propagation.
The next node in the search tree is dominated if there is a g ∈ G and S ∈F
such that

F

Sg ⊆ P.
In the event that we can find suitable g and S , it is safe to backtrack, since we
are in a search state symmetrically equivalent to one considered previously. In
practice, the cost of detecting dominance is often outweighed by the reduction
in search.
SBDD works well in practice: empirical evidence suggests that SBDD can deal
with larger symmetry groups than many other techniques. It is possible to de-
tect dominance without using group theoretic techniques. However, this involves
writing a bespoke detector for each problem, usually in the form of additional
predicates in the constraint logic system. Using computational group theory en-
ables generic SBDD, with the computational group theory system needing only
a generating set for G to be able to detect dominance.
A symmetry breaking technique is called complete if it guarantees never to
return two equivalent solutions. Both SBDD and GE-trees are complete, in fact,
SBDD remains complete even when the dominance check is not performed at
every node, provided that it is always performed at the leaves of the search
tree (i.e. at solutions). This observation allows a trade-off between the cost of
performing dominance checks and the cost of unnecessary search. Another possi-
ble approach is to use an incomplete, but presumably faster, symmetry breaking
technique combined with a separate 'isomorph rejection' step to eliminate equiv-
alent solutions.
The ecient algorithm for breaking value symmetries - GE-tree construction
- can safely be combined with SBDD, as shown in Theorem 13 of [10]. The
algorithm implied by this theorem performs a dominance check, using the full
group G of the CSP L ,ateachnodeofaGE-treefor L under G

Val .
In the next two sections we will identify and discuss a mathematically special,
but common, situation in which we can uncouple variable and value symmetries.
We follow this with preliminary experimental results for a range of symmetry
breaking approaches involving combinations of SBDD and GE-tree methods.