Many symmetry breaking techniques assume that the symmetries of a CSP are given as input in addition to the CSP itself. We present a method that can be used to detect all the symmetries of a CSP. This method constructs a graph that has the same symmetries as the CSP. Then, generators for the symmetry group are computed using a graph automorphism algorithm. This method improves and extends previous work in order to cover global constraints, arithmetic expressions and value symmetries. We show that this method is able to find symmetries for examples that were thought to be too convoluted for automated detection. We also show that the overhead of symmetry detection is quite negligible, even on very large instances. We present a comprehensive set of examples where automated symmetry detection is coupled with symmetry breaking techniques.
Swipe to navigate through the chapters of this book
Please log in to get access to this content
To get access to this content you need the following product:
- Automatic Detection of Variable and Value Symmetries
- Springer Berlin Heidelberg
- Sequence number
Neuer Inhalt/© ITandMEDIA