3
1

I've been looking at the family of MIP's:

\(x_{i,j}\) are continuous non-negative variables for \(i=1,\dots,m, j = 1,\dots,n\)

Maximize \(u\) subject to

\(\sum_i x_{i,j} = n\) for \(i=1,\dots,m\)

\(\sum_j x_{i,j} = m\) for \(j=1,\dots,n\)

\(y_{i,j}\) are binary variables for \(i=1,\dots,m, j = 1,\dots,n\)

and

\(y_{i,j} = 1\) implies that \(x_{i,j} \ge u\)

\(y_{i,j} = 0\) implies that \(x_{i,j} = 0\).


This problem has lots of symmetries – one can permute any of the rows or columns of the matrices \((x_{i,J})\), and \(y_{i,j}\).


In order to break most of the symmetries I add the inequalities

\(\sum_i 2^i y_{i,j} \le \sum_i 2^i y_{i,j+1}\) for \(j=1,\dots,n-1\)

and

\(\sum_j 2^j y_{i,j} \le \sum_j 2^j y_{i+1,j}\) for \(i=1,\dots,m-1\).

I also use, as an alternative, another way of breaking symmetries suggested by Paul Rubin in his comment at https://www.or-exchange.org/questions/8447/finding-an-extreme-ray-with-a-black-box-solver

I've programmed this up in CPLEX on my workstation, and the case for m=17, n=19 solves in about 36 seconds. From combinatorial reasoning, I can come up with a much better upper bound for the variables \(u\) than \(\min(m,n)\). However, when I put in this better upper bound (which in the case I cited, is 6 1/3), cplex ended up taking 152 seconds to solve. In general, I thought that making your polytope tighter was always a good thing. Can someone shed some light on this?

asked 12 Sep '13, 12:23

VictorSMiller's gravatar image

VictorSMiller
343215
accept rate: 0%

2

Yes tighter is in general better. As a general remark, we have not computational wise come so far with MIP as LP yet. So there might be a perfect good explanation, but it's also very likely you just had a case of bad luck in the MIP randomness wheel. Could be a heuristic or cut that magical makes a difference. Try to play with the random seed in cplex, to see if you can make it swing in solution times. If it does, then I would just use what works best and get on with other things :-)

(12 Sep '13, 12:44) Bo Jensen ♦

You could try several different instances of the problem to see if the difference in runtime is by chance or if it is systemic.

(12 Sep '13, 13:11) Austin Buchanan

@Austin: Thanks for the suggestion. I've done a few non-systematic tests with changing the random seed. One choice gets the solve time for the case with the better bound down to 125 seconds, but it also get the case with the original worse bound down to 26 seconds. So the problem I have appears to be extremely sensitive to the random seed.

(12 Sep '13, 13:30) VictorSMiller

Have you tried changing m and n?

(12 Sep '13, 13:42) Austin Buchanan
1

This post by Michael Trick is also relevant http://mat.tepper.cmu.edu/blog/?p=1695

(12 Sep '13, 13:47) Austin Buchanan

@Austin, Yes, the solution time varies quite wildly with different m's and n's. For particular values, extensive combinatorial reasoning has come up with solutions without using MIP, however, I'd like to see what good MIP solving would do.

(12 Sep '13, 13:59) VictorSMiller

@Austin, I tried a few experiments with m=18, n=19. Using my original lexicographic symmetry breakers it took 27 seconds using the better upper bound and 32 seconds without it. Using Paul's alternative, it's still running at 1600 seconds (sorry Paul).

(12 Sep '13, 14:13) VictorSMiller

@Austin, Thanks for the link to Trick's blog post (and the talk by Fischetti that inspired it). I actually looked at last year, but had forgotten about it. I won't now!

(12 Sep '13, 14:15) VictorSMiller
1

I'm with @Bo when it comes to the MIP roulette wheel. Tighter usually is better, but sometimes the solver just happens to hit a useful node/subtree early in the loose formulation but later in the tight formulation. The hare usually beasts the tortoise, but he messes up once and everybody gets excited. I'm still betting the hare.

(14 Sep '13, 19:22) Paul Rubin ♦♦
showing 5 of 9 show 4 more comments

I don't get the problem statement. I don't see how u is constrained.

To be specific, u appears in constraints that relate x and y variables. There are no other constraints on y variables except for symmetry breaking. If you remove these symmetry breaking constraints then you get an unbounded problem.

Something is missing in your description.

link

answered 12 Sep '13, 13:48

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

edited 12 Sep '13, 13:51

@jfpuget: Here's why u is constrained: Note that \(y_{i,j} = 1 \) if and only if \(x_{i,j} > 0\). And some \(x_{i,j}\) must be non zero since \(\sum_j x_{i,j} = m\). However, since it's non-negative this implies that \(x_{i,j} \le m\), and then, since \(y_{i,j} = 1\) this implies that \(u \le x_{i,j}\).

(12 Sep '13, 14:03) VictorSMiller
1

thanks, I read too fast. Have you tried without symmetry breaking constraints? Also, is your upper bound close to the optimal value? Setting the optimal value as upper bound may lead to lots of dual degeneracy, as explained in a post by Paul Rubin http://orinanobworld.blogspot.fr/2013/06/object-constraints-sequel.html. See also this other post by Paul http://orinanobworld.blogspot.fr/2013/05/a-priori-objective-bound.html

(13 Sep '13, 12:48) jfpuget

I've tried a few small cases without the symmetry breaking constraints -- and they all run much more slowly. Thanks for the links to Paul Rubin's blog. In the case of m=17,n=19, the upper bound isn't tight (it's 6 1/3, and the optimum is 5 2/3). I did find that setting probing at very aggressive (3) it reduced the time with the better bound from 2500 seconds to 21 seconds! It also reduced the time for the weaker bound from 36 seconds to 16 seconds.

(13 Sep '13, 13:42) VictorSMiller

@jfpuget: I tried a few cases both with and without the symmetry breaking constraints. For example when m=4, n=9, it takes 0.05 seconds with the symmetry breaking, but 35.68 seconds without. With m=5, n=11 it takes 0.14 seconds with the symmetry breaking constraints, and without I finally killed it after 9200 seconds -- it had found an incumbent with, what I knew was an optimal value, but was stuck trying to get a better bound. So this is one example where symmetry breaking makes a real difference.

(13 Sep '13, 16:19) VictorSMiller
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×191
×71
×8

Asked: 12 Sep '13, 12:23

Seen: 1,099 times

Last updated: 14 Sep '13, 19:22

OR-Exchange! Your site for questions, answers, and announcements about operations research.