Automatic Symmetry Detection and Dynamic Symmetry Breaking for Constraint Programming

Constraint satisfaction and optimisation problems occur frequently in industry and are
usually computationally expensive to solve. Constraint programming is a technique for
solving these difficult problems using specialised algorithms and search heuristics. The
presence of symmetries in constraint problems provides an opportunity to reduce the
computational effort required to solve these problems. To exploit symmetries, a problem
must first be analysed to determine what symmetries are present and then the search
algorithm must be modified to use the known symmetries.

In this thesis we provide contributions to both the research areas of automatically
detecting symmetries and of exploiting them to improve search performance. The auto-
matic detection of symmetries in constraint problems has been studied for some time, but
existing methods can handle realistically-sized problems only by sacrificing the number
and kinds of symmetry they can find. We contribute to this area in two parts. First, we
present a method of automatically detecting the symmetries of a constraint problem that
is capable of finding many small problems in a practical amount of time, and prove its
correctness. Second, we use this method as the foundation of a framework for finding the
symmetries in entire classes of problems. Symmetry detection on classes of problems has
been little studied; our approach greatly improves the practicality of automatic symmetry
detection as the symmetries found apply to many problem instances, small and large.

The exploitation of symmetries for improving search has been the subject of research
for many years, but there is yet to be a method that is easy to use and that gives good
performance under different search heuristics. We present a method of symmetry break-
ing, Lightweight Dynamic Symmetry Breaking (LDSB), that seeks to fill this void. We
describe how LDSB focuses on common symmetries to maximise performance, and show
experimentally that it performs consistently and is competitive with other dynamic sym-
metry breaking methods. Finally, we show how LDSB can be extended to much more
general search techniques.

When considered together, these contributions form the components of an automatic
system for detecting the symmetries of a problem class, and exploiting those symmetries
when solving different instances of that class.