# How can I best handle symmetries in my MIP?

When dealing with mixed-integer-programs with many symmetric solutions it can take very long until the branch-and-bound-tree search is finished because symmetric optimal solutions cannot be pruned. What techniques can I use for a MIP with symmetries to overcome these difficulties?

• 'Many symmetric solutions' - Does this mean many symmetric alternative optima, or a solution with lots of symmetry? May 30 '19 at 23:31

You can add symmetry elimination constraints, like saying that the you want solutions with lower index. For example, you can say something like if $$x_{i+1}$$ is used, then $$x_i$$ must also be used. Note that you might not find a feasible solution if you’re timing out because these constraints cut off an otherwise valid solution. Perhaps you can add them after finding a feasible solution as in branch-and-cut.

You can also trying different branching rules. Orbital branching is the one I know of. Some of these are implemented in SCIP; you just have to activate them by setting a higher priority.

The best option for completely eliminating symmetry is Dantzig-Wolfe reformulation. You do the convexification and then you end up with multiple "convexity constraints" in the master problem. Then you sum them up, so that there is only one. My colleague Marco Lübbecke is one of the world's authority on this. He has a great tutorial.

• Edward, can you provide one or two references or tutorials for each of these ideas? May 30 '19 at 23:38
• Done :) (Need more characters) May 31 '19 at 0:24
• Why do you need more characters? I'm confused... May 31 '19 at 0:36
• We need a minimal of 15 characters to post a comment. May 31 '19 at 0:39
• Oh, I see. Edward was saying "(need more characters)" to provide the extra characters that he needed in that comment. Very meta. (I thought he was saying he needed more characters in the answer.) May 31 '19 at 2:41

I think that the best survey of symmetry in IP was given by Francois Margot: https://link.springer.com/chapter/10.1007/978-3-540-68279-0_17

• For people not having access to the paper is it possible to resume the key takeaways from the paper? Jul 1 '19 at 18:15

Here's a simple example of a symmetry-breaking constraint. Consider the bin-packing problem: We want to pack $$N$$ items into the smallest number of bins (up to $$M$$ bins). Item $$n$$ has size $$a_n$$, and the size of each bin is $$v$$. Let $$x_{mn} = 1$$ if we put item $$n$$ in bin $$m$$ (0 otherwise), and let $$y_m = 1$$ if bin $$m$$ is used (0 otherwise).

The problem can be formulated as: \begin{alignat}{2} \text{minimize} \quad & \sum_{m=1}^M y_m && \\ \text{subject to} \quad & \sum_{m=1}^M x_{mn} = 1 &\quad& \forall n=1,\ldots,N \\ & \sum_{n=1}^N a_n x_{mn} \le vy_m && \forall m=1,\ldots,M \\ & x_{mn}, y_m \in \{0,1\} && \forall m=1,\ldots,M, n=1,\ldots,N \end{alignat} The objective function calculates the total number of bins used; the first constraint says every item must be placed in a bin; and the second constraint says the total size of items placed in bin $$m$$ can't exceed $$v$$, and must be 0 if $$m$$ is not used.

There's a lot of symmetry in this problem, because the bins are identical. For any solution, we can just "rotate" the bins and we get a different solution with the same objective function value. For example, suppose there are 3 items, with sizes 7, 3, and 6, respectively; and 4 bins of size 10. The optimal solution uses 2 bins, but there are several such solutions:

• [1,2] [3] [] [] (items 1 and 2 in bin 1; item 3 in bin 2; and bins 3 and 4 empty)
• [] [1,2] [3] []
• [] [] [1,2] [3]
• [] [1,2] [] [3]
• etc.

This symmetry makes it hard for the solver to prove that the optimal solution is indeed optimal.

To break the symmetry, we can add constraints that arbitrarily require us to use lower-indexed bins first. For example, the constraint $$y_{m+1} \le y_m$$ says that we can't use bin $$m+1$$ if we're not also using bin $$m$$. So the first solution above is feasible, but all the others are infeasible.

We could also add symmetry-breaking constraints that require lower-indexed items to be in lower-indexed bins, so [1,2] [3] [] [] would be feasible but [3] [1,2] [] [] would not.

Automatic methods for symmetry-breaking like the ones that @Edward Lam mentioned seem to be getting more and more powerful, but it's also often worth examining your specific problem to see if symmetries can be identified and broken.

• Do you have a comment on my "answer",(which is really other people's answers)? Sep 15 '20 at 12:05
• @MarkL.Stone Very interesting, although I am by no means an expert on this topic so I would defer to the experts in your thread. Sep 17 '20 at 18:16

Here is contrary advice provided by folks running CO@WORK2020 . I referenced this thread.

Mark L. Stone There is a large folklore, see for instance How can I best handle symmetries in my MIP? , that symmetries in MILP models are bad from a solver computation time perspective, Yet the advice in a lecture Monday was pretty much not to make symmetry-breaking changes to a model. Is neither "side" always or usually right?

Victorien Cornet @Mark L. Stone I understood it as "the program is most likely far better than you at detecting symmetries, and will have a not costly method to detect them and deal with them. As such, you should let him do it, because if by removing 50% of symmetry, you also hide the other 50%, you will make the problem computationally worse.

Paula Fermin @Mark L. Stone There is a very good paper by Fischetti and Liberti (2012), with the title "Orbital Shrinking", where they claim that symmetry is a beneficial feature that should be exploited. Instead of breaking it with artificial constraints (which they say it should only be done as a last resort) they capture it in the formulation. As far as I know CPLEX and Gurobi use algorithms based on these ideas to exploit symmetry rather than breaking it. I'm not sure about other solvers. (edited)

Timo Berthold <organizer/lecturer at CO@WORK2020/developer at FICO XPRESS> Xpress and SCIP do as well. I am on Matteo's and Leo's page that in most cases, solvers would capture the whole symmetry structure and handle it accordingly, while user constraints easily (not always) fix only a part of the symmetry, but destroy the structure as a whole.That being said, if the modeler has a background in group theory and completely knows the symmetry structure of their problem, they might be able to handle things the solver can't. As one general example, note that solvers consider FORMULATION symmetry, which implies SOLUTION symmetry. Solution symmetry is a stronger concept. If your formulation is solution-symmetric, but not formulation-symmetric, it is up to you to handle this.