{"id":1695,"date":"2012-09-25T17:19:25","date_gmt":"2012-09-25T21:19:25","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1695"},"modified":"2012-09-25T17:19:25","modified_gmt":"2012-09-25T21:19:25","slug":"fischetti-speeds-up-optimization-with-randomness","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2012\/09\/25\/fischetti-speeds-up-optimization-with-randomness\/","title":{"rendered":"Fischetti Speeds Up Optimization with Randomness"},"content":{"rendered":"

\"\"<\/a>I just got back from a very nice workshop<\/a> on “Matheuristics” held outside of Rio de Janeiro, Brazil. \u00a0Matheuristics is the combination of optimization and heuristics. \u00a0For instance, I talked about large scale local search for sports scheduling problems (among other things). \u00a0In this approach, portions of a sports schedule are fixed, and you optimize over the rest using integer programming. \u00a0This has aspects of both metaheuristics (large scale local search) and optimization (integer programming).<\/p>\n

I greatly enjoyed the workshop and thank Celso Ribeiro<\/a> for organizing it and inviting me. \u00a0It was a small workshop, with perhaps 40 participants, with a single track of papers. \u00a0For the first time in years I attended every talk at a conference! \u00a0Try doing that at INFORMS<\/a>!<\/p>\n

My favorite talk was given by Matteo Fischetti<\/a>\u00a0of the University of Padova. \u00a0The talk, entitled “Erraticism in tree\u00a0search\u201d was a real eye opener in terms of my understanding of how branch-and-bound on integer programs performs in practice. \u00a0I’m going to paraphrase some of the key points of the talk. \u00a0None of the numbers in the following are exactly what Matteo presented, but this is close enough to get the idea across.<\/p>\n

Here’s the setup: \u00a0Matteo claims to have a new cut for general mixed integer programs. \u00a0It is parameterized, so he can actually create 10 different versions of that cut. \u00a0He downloaded the MIPLIB 2010<\/a> benchmarks and some other benchmarks he found, ran default CPLEX<\/a> on them, and limited his test to hard, but not insolvable instances (tossing out all instances solved by default CPLEX in under 100 seconds or requiring more than 1000 seconds). \u00a0This left a test bed of 38 instances.<\/p>\n

When Matteo solved the testbed using each of the ten cuts (separately), he found something amazing: \u00a0a single cut often greatly decreased computation time. \u00a0The (geometric) average decreases over the testbed relative to default CPLEX for the ten different parameterizations were:<\/p>\n\n\n<\/colgroup>\n\n\n\n
Parametrization<\/td>\n1<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n5<\/td>\n6<\/td>\n7<\/td>\n8<\/td>\n9<\/td>\n10<\/td>\n<\/tr>\n
Decrease<\/td>\n<\/td>\n12%<\/td>\n14%<\/td>\n25%<\/td>\n4%<\/td>\n-0.50%<\/td>\n32%<\/td>\n15%<\/td>\n12%<\/td>\n6%<\/td>\n33%<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Wow! \u00a0These cuts are great! \u00a0Cut 5 had a bit of an increase in time, but it turned out that cut was kind of a dummy. \u00a0Cut 5 took a random permutation of the non-negative integer variables and added a constraint\u00a0\u03a3 xi\u00a0\u2265 -1. This constraint clearly doesn’t do anything: CPLEX throws it away during preprocessing.<\/p>\n

But look at Cut 10. \u00a0It decreased computation time by 33%. \u00a0It is amazing! \u00a0Cut 10 took a random permutation of the non-negative integer variables and added a constraint\u00a0\u03a3 xi\u00a0\u2265 -1. And that seems to work really well!<\/p>\n

Hold on…. What’s going on here? \u00a0In fact, each of the cuts is simply a random permutation of the variables and a redundant constraint. \u00a0How can that have any effect?<\/p>\n

CPLEX (as with Gurobi <\/a>or any other solver) has a certain “randomness” in its operation. \u00a0This is not random in the sense that the final answers are not optimal, but rather the exact operation of the algorithm may depend on things like the ordering of the variables. So, for instance, if a solution to a linear program has multiple optimal solutions, the exact solution reported can depend on which variable is first in the internal ordering of variables. \u00a0And, of course, the exact solution reported can then affect the branch and bound tree (since different variables might have fractional values).<\/p>\n

If you change the internal ordering of the variables, you can change the operation of the branch and bound algorithm. \u00a0Adding the redundant cut changed the internal ordering of the variables, so the timing results could vary. \u00a0 Not every instance has this aspect. \u00a0Some have relatively consistent computation time independent of the ordering. \u00a0But some instances vary a lot based on the ordering.<\/p>\n

This is insight 1: \u00a0branch and bound timings may vary a lot due just to the random choices of the algorithm.<\/p>\n

If your computation time is too long, try permuting the variables. \u00a0If you see lots of variation in computing time, perhaps it it is worth running multiple instances in parallel with different variable orderings (or internal random number seeds) in the hopes that one instance will solve much faster than the others.<\/p>\n

This makes me wonder how many past papers showing that an approach is useful are simply showing different (good) random draws from the search tree? \u00a0And how many good ideas have been discarded due to “bad luck” from the random number generator?<\/p>\n

But this still leaves a puzzle: \u00a0almost every<\/em> random ordering is better than default CPLEX. \u00a0 Does this mean that you should at least randomly generate an variable ordering? \u00a0One gentleman at the conference, vibrating with excitement, thought he had the justification for this:<\/p>\n

Since most of these instances come from real problems, perhaps there is something about the way people formulate problems that leads to problems with the solution code. As I code, I would normally generate all of one type of variable (say, the “x” variables), then the “y” variables, then the “z” variables. \u00a0This must be messing up CPLEX. \u00a0What a great insight!<\/p><\/blockquote>\n

That hyperventilating gentleman was me. \u00a0And Matteo quickly and firmly showed that I was wrong. \u00a0How could almost all of the orderings do better than default CPLEX? \u00a0Look back, the hint is there…..<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

How did we get our instances? \u00a0Let me quote myself:<\/p>\n

He downloaded the MIP2010 benchmarks and some other benchmarks he found, ran default CPLEX on them, and limited his test to hard, but not insolvable instances (tossing out all instances solved by default CPLEX in under 100 seconds or requiring more than 1000 seconds).<\/p><\/blockquote>\n

In doing this, he biased the sample! \u00a0Anything default CPLEX did well on (under 100 seconds), we threw out! \u00a0So the sample was made up of things that default CPLEX did not do well on. \u00a0It is no wonder that “Cut 1” had an advantage. \u00a0If we had run all the instances on “Cut 1” and threw out anything it did well on, it would turn out the default CPLEX would do better than “Cut 1”. \u00a0If you toss out instances that an algorithm works well on, don’t be surprised if it does poorly on the rest.<\/p>\n

So this is insight 2: \u00a0if you want to compare algorithms A and B, make sure the definition of the testbed does not depend on which gets label A and which gets label B.<\/p>\n

I can’t tell you the number of times I have read computational papers that make the bias mistake. \u00a0And I rarely noticed it. \u00a0I will now!<\/p>\n

Of course, Matteo doesn’t make mistakes like this in his work: \u00a0this presentation was an extremely effective way of showing how easy it is to make this error.<\/p>\n

I cannot do full justice to Matteo’s talk: \u00a0there were many more insights and surprises. \u00a0The associated paper (with Michele Monaci) is here<\/a>. \u00a0And if you get a chance to see him give the talk, do so!<\/p>\n

After that talk, I will never look at computation in integer programming the same way again. \u00a0That presentation alone was worth the flight to Brazil!<\/p>\n

Added 9\/26: <\/strong>\u00a0Matteo has kindly provided his slides, which are available here<\/a>.<\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

I just got back from a very nice workshop on “Matheuristics” held outside of Rio de Janeiro, Brazil. \u00a0Matheuristics is the combination of optimization and heuristics. \u00a0For instance, I talked about large scale local search for sports scheduling problems (among other things). \u00a0In this approach, portions of a sports schedule are fixed, and you optimize … Continue reading “Fischetti Speeds Up Optimization with Randomness”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,29,46],"tags":[],"class_list":["post-1695","post","type-post","status-publish","format-standard","hentry","category-conferences","category-integer-programming","category-research"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1695","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1695"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1695\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1695"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1695"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1695"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}