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

Table 1. Experimental results

n 5 6 7 8

solutions 1 0 1 0

GAP 0.39 0.48 1.01 112.44

SBDD ECL 0.19 0.48 7.35 814.92

Σ 0.68 0.96 8.36 927.36

GAP 0.42 0.37 1.49 127.15

GEtree+iso ECL 0.09 0.35 12.01 1677.26

Σ 0.51 0.72 13.50 1804.73

GAP 0.42 0.52 1.51 195.15

GEtree+SBDDfull ECL 0.06 0.27 6.79 935.74

Σ 0.48 0.79 8.30 1131.19

GAP 0.77 0.93 3.96 930.77

GEtree+SBDDval ECL 0.03 0.32 6.65 1146.46

Σ 0.80 1.25 10.61 2077.23

is not competitive: the search tree is still large (since only value symmetries
are being broken), with expensive variable symmetry breaking being postponed
until the entire tree is searched. Interestingly, the results for GE-tree construction
combined with SBDD on the complement of the value symmetries are not as good
as expected. This approach combines polynomial time value symmetry breaking
with dominance detection in a smaller algebraic structure than the full symmetry
group. Therefore, on a heuristic level, we expect faster symmetry breaking than
for GE-trees and full-group SBDD. Further experiments are required to pinpoint
the reasons why the time gain is not as great as expected: the combination of
symmetry breaking methods is, in general, an unexplored research area.

6 Conclusions

Symmetry breaking in constraint programming is an important area of interplay
between artificial intelligence and symbolic computation. In this paper we have
identified a number of important special structures and cases that can arise in
the action of a symmetry group on the literals of a constraint problem. We have
described a number of ways in which known symmetry breaking methods can
be safely combined and described some new methods exploiting these newly
identified structures.
Our initial experimental results demonstrate the applicability of our theoret-
ical results, with more work to be done to overcome the apparent overheads of
combining more than one symmetry breaking technique during the same search
process. Other future work includes assessment of new heuristic approaches, in-
cluding problem reformulation (to obtain a CSP with a more desirable symmetry
group than that of a standard CSP model) and using dominance detection only
at selected nodes in the tree (as opposed to every node, as currently imple-
mented). We also aim to investigate both the theoretical and practical aspects
of further useful ways of decomposing the symmetry group of a CSP.