[gecode-users] Breaking symmetries with LDSB in Matrix Model.

[Chris Mears]

> But in my problem i need functions for breaking only specified rows
> or specified columns that are interchangeable, for example : rows 4
> and 7 of the matrix are interchangeable, or for example: column 2 and
> 5 only are interchangeable and not all rows are interchangeable and
> not all columns are interchangeable.

Here is how you might interchange only two rows of a matrix.  I took
the BIBD example and kept only the row-sum and column-sum constraints:

  BIBD(const BIBDOptions& o)
    : opt(o), _p(*this,opt.rows*opt.cols,0,1) {
    Matrix<BoolVarArray> p(_p,opt.cols,opt.rows);

    // r ones per row
    for (int i=0; i<opt.rows; i++)
      linear(*this, p.row(i), IRT_EQ, opt.r);

    // k ones per column
    for (int j=0; j<opt.cols; j++)
      linear(*this, p.col(j), IRT_EQ, opt.k);

For a 3x3 matrix with 1 one per row and column, this has 6 solutions:

		1 0 0 
		0 1 0 
		0 0 1 

		1 0 0 
		0 0 1 
		0 1 0 

		0 1 0 
		1 0 0 
		0 0 1 

		0 1 0 
		0 0 1 
		1 0 0 

		0 0 1 
		1 0 0 
		0 1 0 

		0 0 1 
		0 1 0 
		1 0 0 


Then I put the first row and second row in a BoolVarArgs object and
give it as a variable sequence symmetry:

    Symmetries s;
    BoolVarArgs a2;
    a2 << p.row(0);
    a2 << p.row(1);
    s << VariableSequenceSymmetry(a2, opt.cols);

Now there are only three solutions:

		1 0 0 
		0 1 0 
		0 0 1 

		1 0 0 
		0 0 1 
		0 1 0 

		0 1 0 
		0 0 1 
		1 0 0 

> an other case that i need is: where we have the following
> permutations of rows of a matrix ( rotation of rows):
> 
>                         row 1   takes the content of   row 2
>                         row 2   takes the content of   row 3
>                                                       .
>                                                       .
>                         row i     takes the content of   row (i+1) 
>                                                       .
>                                                       .
>                        row n     takes the content of   row 1

For this case you can do something similar:

    BoolVarArgs a;
    for (int i = 0 ; i < opt.rows ; i++) {
      a << p.row(i);
    }
    for (int i = 0 ; i < opt.rows ; i++) {
      a << p.row((i+1)%opt.rows);
    }
    s << VariableSequenceSymmetry(a, opt.rows*opt.cols);

Now there are only two solutions:

		1 0 0 
		0 1 0 
		0 0 1 

		1 0 0 
		0 0 1 
		0 1 0 

The two symmetries could be combined too.

Note that the number of solutions found can depend on the search order;
if you do the same exercise with INT_VAL_MIN instead of MAX, you'll get
different results.