12
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ 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.) $\endgroup$ – LarrySnyder610 Jun 3 '19 at 20:57
  • $\begingroup$ 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? $\endgroup$ – LarrySnyder610 Jun 3 '19 at 21:13
  • 5
    $\begingroup$ I still do not quite get what the decision variables are and what are the parameters? Can you state the full problem? $\endgroup$ – JakobS Jun 4 '19 at 12:20
  • 2
    $\begingroup$ the problem, as stated, is trivial to solve: put zeros everywhere. what are the constraints? $\endgroup$ – Marco Lübbecke Jun 12 '19 at 20:23
  • 1
    $\begingroup$ @MarcoLübbecke There are of course more constraints. In this question I'm only asking about symmetry-breaking though. $\endgroup$ – Simon Jun 13 '19 at 21:44
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.