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 under preparation, 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 for Gecode is still evolving, but it is usable in its current state for people willing to experiment. The latest version is available here and works with Gecode version 3.3.1.

(Note: a version that works with Gecode 3.4.0 is available too, but it does not yet work with set variables. LDSB is being prepared for inclusion in the next major release of Gecode, which will be version 4.0.0.)

How to use LDSB with Gecode

The simplest way to see how LDSB is used is to examine one of the examples in the tests directory included with LDSB. The steps needed to add LDSB to your model are:

First, put ldsb.hh somewhere in your compiler’s include path and compile ldsb.cc. Next, in your model include ldsb.hh and create a Symmetries object, and populate it with symmetry objects, e.g.:

// Array of variables on which the symmetry acts.

IntVarArray xs;

ExampleModel() : xs(*this, 4, 0, 3)
{
    // Model constraints.
    distinct(*this, xs);

    // Symmetries object, containing one symmetry.
    Symmetries s(1);

    // Values are interchangeable.
    s[0] = values_interchange(*this, xs);

Call the branch function and pass the Symmetries object.

    branch(*this, xs, INT_VAR_NONE, INT_VAL_MIN, s);
}

Compile your model and link with ldsb.o.