13
$\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$
7
  • 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$ Commented Jun 3, 2019 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$ Commented Jun 3, 2019 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
    Commented Jun 4, 2019 at 12:20
  • 2
    $\begingroup$ the problem, as stated, is trivial to solve: put zeros everywhere. what are the constraints? $\endgroup$ Commented Jun 12, 2019 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
    Commented Jun 13, 2019 at 21:44

1 Answer 1

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 and acknowledge you have read our privacy policy.

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