16
$\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 at 23:31
15
$\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.

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

$\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 at 18:15
11
$\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.

$\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.