# Symmetry-breaking ILP constraints for square binary matrix

## 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:

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:

• 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?

• 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 3 '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 3 '19 at 21:13
• I still do not quite get what the decision variables are and what are the parameters? Can you state the full problem? – JakobS Jun 4 '19 at 12:20
• the problem, as stated, is trivial to solve: put zeros everywhere. what are the constraints? – Marco Lübbecke Jun 12 '19 at 20:23
• @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

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.