13

Setup

I have a binary $N \times N$ matrix. The objective is to minimize the number of ones in the matrix, subject to various constraints. This leads to symmetries by rotating 90 degrees and/or mirroring (along the axis and diagonals). Here's an example:

8x8 matrix example

Given the objective function, this matrix has the same objective value as a rotated or mirrored copy of the same matrix. The model performance improves if I add symmetry-breaking constraints, especially on infeasible instances. I sum the quadrants the following way and generate symmetry-breaking constraints:

Quadrants

  • To account for rotations and mirroring:
    • $ q_1 \geq q_2 $ (A1)
    • $ q_1 \geq q_3 $ (A2)
    • $ q_1 \geq q_4 $ (A3)
  • To account for diagonal mirroring:
    • $ q_2 \geq q_3 $ (B1)

Question

Are there more efficient/simpler alternatives to state the symmetry-breaking constraints, for example with fewer non-zero coefficients?

Simon
  • 1,132
  • 8
  • 16
  • 4
    Would it be practical to add a very small example (e.g., 4x4)? That might make it easier to see what's going on in each of the constraint sets. (For example, I can't quite tell where all of the non-zero coefficients are.) – LarrySnyder610 Jun 03 '19 at 20:57
  • Thanks for the example! But I can't see the symmetry. If I rotate the matrix 90 degrees it's not equivalent to the original. What am I missing? – LarrySnyder610 Jun 03 '19 at 21:13
  • @LarrySnyder610 Sorry, you're right. My question was not clearly stated. Mirrored solutions are equivalent objective-wise. I tried to clarify. – Simon Jun 03 '19 at 21:18
  • 5
    I still do not quite get what the decision variables are and what are the parameters? Can you state the full problem? – JakobS Jun 04 '19 at 12:20
  • 2
    the problem, as stated, is trivial to solve: put zeros everywhere. what are the constraints? – Marco Lübbecke Jun 12 '19 at 20:23
  • 1
    @MarcoLübbecke There are of course more constraints. In this question I'm only asking about symmetry-breaking though. – Simon Jun 13 '19 at 21:44
  • Could you do this by starting with e.g. the top left element and check which other elements could be reached by rotation and mirroring (i.e. the orbit in group theory). For these elements you could specify an (artificial) order in which the elements should be arranged. This could lead to e.g. $x_{11} \leq x_{18} \leq x_{88} \leq x_{81}$. Do this for all other elements till your grid is completely covered. – JakobS Jun 14 '19 at 09:01

1 Answers1

5

I believe you have accounted for the rotation, mirroring adequately. The diagonal mirroring may be inadequate.

Unless it is going to be addressed in your other constraints, you also need to fix the location of $q_4$ relative to either $q_2$ or $q_3$. $$q_2 \ge q_4$$ Without the above constraint, I believe, it is possible for the diagonal mirroring to still exist.

prash
  • 338
  • 1
  • 7