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 automatic 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 breaking, 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 symmetry 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.