19
$\begingroup$

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?

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

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Edward, can you provide one or two references or tutorials for each of these ideas? $\endgroup$ – LarrySnyder610 May 30 '19 at 23:38
  • 1
    $\begingroup$ Done :) (Need more characters) $\endgroup$ – Edward Lam May 31 '19 at 0:24
  • $\begingroup$ Why do you need more characters? I'm confused... $\endgroup$ – LarrySnyder610 May 31 '19 at 0:36
  • 1
    $\begingroup$ We need a minimal of 15 characters to post a comment. $\endgroup$ – Siong Thye Goh May 31 '19 at 0:39
  • $\begingroup$ 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.) $\endgroup$ – LarrySnyder610 May 31 '19 at 2:41
18
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ For people not having access to the paper is it possible to resume the key takeaways from the paper? $\endgroup$ – Renaud M. Jul 1 '19 at 18:15
12
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Do you have a comment on my "answer",(which is really other people's answers)? $\endgroup$ – Mark L. Stone Sep 15 at 12:05
  • $\begingroup$ @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. $\endgroup$ – LarrySnyder610 Sep 17 at 18:16
5
$\begingroup$

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.

| improve this answer | |
$\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.