[gecode-users] Toroidal symmetry breaking (with LDSB or not)

[Chris Mears]

Hello Martin,

> Hence my questions: is it possible to use LDSB to implement symmetry
> breaking "toroidal"? If not, is it possible to implement symmetry
> breaking "toroidal" in another way?

You can use LDSB to break this symmetry, which is the composition of
two "cyclic" symmetries. If your variables are in a matrix "m":

    Symmetries syms;
    
    IntVarArgs rows;
    for (int r = 0; r < m.height(); r++)
      rows << m.row(r);
    for (int r = 0; r < m.height(); r++)
      rows << m.row((r+1) % m.height());
    syms << VariableSequenceSymmetry(rows, m.width()*m.height());

    IntVarArgs cols;
    for (int r = 0; r < m.width(); r++)
      cols << m.col(r);
    for (int r = 0; r < m.width(); r++)
      cols << m.col((r+1) % m.width());
    syms << VariableSequenceSymmetry(cols, m.width()*m.height());

The idea is that for the rows you have a variable sequence symmetry,
where the variables in the first sequence map to the corresponding
variables in the second one:

  a b c d e f g h i j k l m n o p
  e f g h i j k l m n o p a b c d

(i.e. a -> e, b -> f, etc.)

And similar for the columns.

Another way to break the symmetry, without LDSB, is to fix the position
of the smallest element; e.g. force the smallest element to be in the
top-left corner.  You can do this by posting constraints

  m(0,0) <= m(0,1)
  m(0,0) <= m(0,2)
  etc.

Are the variables in the square array constrained to be all different?
If so, you can strengthen those constraints into "strictly less than".
If they're all different and form a permutation (i.e. the number of
values in their domain is equal to the number of variables) then you
can simply fix the top-left variable to the smallest value;
e.g. "m(0,0) = 1".

Cheers,
Chris