How can I best handle symmetries in my MIP?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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

https://app.slack.com/client/T018492NU8P/C018R5MJ8J1/thread/C018R5MJ8J1-1600131609.111100

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.

Edit: Additional Q&A in the above linked thread

Mark L. Stone Does it make sense to give the solver a chance to deal with the symmetries. And if it seems to have difficulties, to then consider adding symmetry-breaking constraints?

Timo Berthold @Mark L. Stone: Trying out different approches is hardly ever a bad idea. I believe that is what everyone can agree on (and what both sources explicitly stated, while coming to a different conclusion what the first choice would be)

Paula Fermin @Timo Berthold What is the difference between solution symmetry and formulation symmetry?

Timo Berthold @Paula Fermin Take an IP min Ax = b x \in Z^n. Let F be the set of feasible solutions of this IP. Let p be a permutation of (1...m) and q be a permutation of (1..n). If you apply p to Ax=b and subsequently q to the matrix permuted that way, this will give you a new IP A'x = b' with a new set of feasible solutions (same cardinality of course) F'. We call (p,q) a formulation symmetry if A=A' and b=b'. Of course this implies F=F'. The case that F=F' is called solution symmetry and it does not imply anything on the relation between A,b and A',b'. Of course this can be extended to MIP and the case that we have an objective c, but I wanted to keep notation short.

Answer 5

Jeff Linderoth thinks 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 Here is my summary of it.

• Groups are complicated and varied. While groups can be symmetric also non symmetric groups (such as permutation groups) can express symmetries on the problem.
• Symmetry detection is hard. In fact as hard as solving MILPs (or more precisely checking whether a different MILP has a solution). Domain knowledge is helpful. A promising approach is to instead rely on symmetries of the linear relaxation of the MILP. Users can make detecting symmetries impossible by removing only part of a symmetry with a constraint they add.
• Perturbing the objective slightly to remove symmetries is a bad idea. Today there are solvers with symmetry detection. Use them!
• Variable fixing is useful. It might reveal new permutations which are a tractable type of symmetry. Yet even variable fixing (which shrinks the problem as opposed to cuts which grow the size of the constraint matrix) might slow a symmetry aware solver. You'll probably have to try out. Fixing variables might even weaken the relaxation compared to what a symmetry aware solver would have discovered.
• Objective values can often break symmetries. Consider the TSP without cost for an example. The study of these constraints only polytopes does not yet seem to have yielded usable insight how to solve problems with objective values. Bin packing, cutting stock, scheduling on identical machines, graph coloring (either vertex-coloring or edge-coloring), and graph partitioning problems are partitioning type problems. Those have permutation of column type symmetry if the objective vector $c$ has the same symmetries. In addition row permutation symmetries occur with symmetries in constraints (such as two objects having the same dimensions).
• Dantze-Wolfe decomposition breaks column symmetries well, usually needs column generation though. Pricing problem usually domain specific.
• Row wise symmetries with a Partitioning orbitope which has a description as shifted column inequalities.
• In case the number of partitions is to be minimized consider Asymmetric representatives. See Campelo M., Campos V., Correa R

The fundamental region $F$ is the smallest set of points which allow you to cover the entire $\mathbb{R}^n$ under application of group operations. Smallest in the sense that no group operation maps from the interior of the $F$ into the interior of $F$. A fundamental region intersect with the feasible region of the MILP contains an optima. With a huge number of inequalities one can define the fundamental region. This usually impractical. There a ways to relax this construction.

• Little is know about how construct a nice $F$ or relaxation of $F$ beyond particular problem classes. Due to interaction with other components of MILP solvers any discussion of nice of efficient becomes drowned by other concerns and cross interactions such as variable choice.

• Margot presents this rule of thumb: For problems with a symmetry group of order up to a few thousands of permutations, dynamic symmetry breaking might be very effective. Larger than, a million, dynamic symmetry breaking inequalities needs to be coupled with other symmetry breaking techniques to be effective.

• Assigning power of two weights to binary variables allows for lexicographic ordering and breaking of permutations. However the number of such breaks is sometimes to huge to be beneficial used statically. Symmetry handling in the solver can not be replaced with mere problem reformulation in practice.

• Dynamic symmetry breaking uses partial assignments and remove all isomorphic partial assignments from the search sub-tree. Those cuts are in general only valid for the sub-problems subject to the partial assignment.

• Constraint programmings stronger clauses lend themself to dynamic symmetry breaking. Lexicographic ordering can be expressed without needing big coefficients that might cause numerical problems.

• Partitioning weaker than splitting weaker than minimum index splitting as branching rules.

• Fixing the order of variables to prune leads to good result compared to symmetry unaware solvers, however can leave orders of magnitude of speed up on the table as information from domain reduction technique gained during the solve is not used.

• Domain reduction techniques together with symmetry must preserve that one optimal solution that is lexicomax in its orbit under G remains feasible.

• The Schreier-Sims representation is an essential tool and employed in group representation and group membership detection. IsoP by Margot F. and SBS by Brown C.A., Finkelstein L., Purdom P.W.: are such algorithms. SBDD also exists and is implemented by Gent I. P., Harvey W., Kelsey T., Linton S. There is no good comparison of those approaches.

• In symmetric problems even faulty algorithms may find optimal solutions, however they may fail to find a particular isomorphic solution or return multiple isomorphic solutions when requested not to so asking for all isomorphic solutions is a useful debugging tool.

• different variable choices might yield very different symmetry group complicated the choice of problem formulation

• Automatic symmetry detection in nodes of the branch and bound tree is not worth it