Symmetry breaking for constraint satisfaction problems (CSPs) has attracted considerable attention in recent years. Various general schemes have been proposed to eliminate symmetries. In general, these schemes may take exponential space or time to eliminate all the symmetries. We identify several classes of CSPs that encompass many practical problems and for which symmetry breaking for various forms of value and variable interchangeability is tractable using dedicated search procedures or symmetry-breaking constraints that allow nogoods and their symmetrically equivalent solutions to be stored and checked efficiently.

This paper reconsiders the problems of discovering symmetries in constraint satisfaction problems (CSPs). It proposes a compositional approach which derives symmetries of the applications from primitive constraints. The key insight is the recognition of the special role of global constraints in symmetry detection. Once the symmetries of global constraints are available, it often becomes much easier to derive symmetries compositionally and efficiently. The paper demonstrates the potential of this approach by studying several classes of value and variable symmetries and applying the resulting techniques to two non-trivial applications. The paper also discusses the potential of reformulations and high-level modeling abstractions to strengthen symmetry discovery.

Symmetry breaking in CSPs has attracted considerable attention in recent years. Various general schemes have been proposed to eliminate symmetries during search. In general, these schemes may take exponential space or time to eliminate all symmetries. This paper studies classes of CSPs for which symmetry breaking is tractable. It identifies several CSP classes which feature various forms of value interchangeability and shows that symmetry breaking can be performed in constant time and space during search using dedicated search procedures. Experimental results also show the benefits of symmetry breaking on these CSPs, which encompass many practical applications.