Symmetry in Constraint Programming

Model Symmetry Detection

In the paper “A Novel Approach For Detecting Symmetries in CSP Models”, we describe a method of detecting symmetries in constraint models, with some experiments. In an extended version of the paper, titled “A method for detecting symmetries in constraint models and its generalisation”, we have included some more problems. This expanded set of models is available here.

The detection implementation itself is available too, but installing it for your own use might require some customization. Please if you are interested.

Lightweight Dynamic Symmetry Breaking (LDSB)

LDSB is a dynamic symmetry breaking method for constraint programming systems. Its theoretical details are explained in our workshop paper “Lightweight Dynamic Symmetry Breaking”; on this page you will find information on how to obtain and use LDSB with the Eclipse and Gecode systems.

Eclipse

LDSB is included with recent builds of Eclipse. Examples of use are given in the Eclipse documentation (e.g. this simple example).

Gecode

LDSB is included in recent versions of Gecode. There are instructions for using it in the Gecode documentation, “Modeling and Programming in Gecode.” There are also some examples included with Gecode that show how to use LDSB.