George Nemhauser and Laurence Wolsey win von Neumann Theory Prize

twitter report has George Nemhauser of Georgia Tech winning the von Neumann Theory Prize from INFORMS.

 

Turns out that you can confirm this at the online conference program:  George Nemhauser and Laurence Wolsey are this year’s von Neumann Prize winners.  This is great news!  George and Laurence are two of my favorite people in the field.  I know George better than Laurence, since he and I are partners in our small sports scheduling company, so I work with him pretty closely.  And I did take a few courses from him when I was a doctoral student at George Tech a century or two ago.   I have interacted often with Wolsey at conferences, and he was kind enough to host me in Louvain years ago. The book George and Laurence wrote is a classic of integer programming and I am actually stunned they did not receive this award years ago.

But this is my blog, not George or Laurence’s, so let me say two things about me in this context:

  1. George and I have a paper that we wrote back in the late 1990s on scheduling Atlantic Coast Conference basketball.  It is dated now, of course (you can solve this problem in seconds rather than hours), but it remains one of my favorite papers, and I think it was pretty influential in kindling interest in sports scheduling optimization.  I wrote it over a 3 day period while snowed in during a year I spent at MIT.  The published version is almost identical to what I wrote in those three days.  I see it is one of George’s top 15 cited papers, but that probably is not the reason he got the von Neumann.  Note that George’s most cited work is his textbook with Wolsey:  Google Scholar is a bit confused about this.
  2. Last year’s winner of the von Neumann was Gerard Cornuejols, who is my colleague at the Tepper School.  Looks like “closeness to Michael Trick” is a key criterion for the von Neumann, though actually being Michael Trick is too close to get the bonus points.

Assuming the rumor is true, Congratulations George and Laurence!

 

Fischetti Speeds Up Optimization with Randomness

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

I greatly enjoyed the workshop and thank Celso Ribeiro for organizing it and inviting me.  It was a small workshop, with perhaps 40 participants, with a single track of papers.  For the first time in years I attended every talk at a conference!  Try doing that at INFORMS!

My favorite talk was given by Matteo Fischetti of the University of Padova.  The talk, entitled “Erraticism in tree search” was a real eye opener in terms of my understanding of how branch-and-bound on integer programs performs in practice.  I’m going to paraphrase some of the key points of the talk.  None of the numbers in the following are exactly what Matteo presented, but this is close enough to get the idea across.

Here’s the setup:  Matteo claims to have a new cut for general mixed integer programs.  It is parameterized, so he can actually create 10 different versions of that cut.  He downloaded the MIPLIB 2010 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).  This left a test bed of 38 instances.

When Matteo solved the testbed using each of the ten cuts (separately), he found something amazing:  a single cut often greatly decreased computation time.  The (geometric) average decreases over the testbed relative to default CPLEX for the ten different parameterizations were:

Parametrization 1 2 3 4 5 6 7 8 9 10
Decrease 12% 14% 25% 4% -0.50% 32% 15% 12% 6% 33%

Wow!  These cuts are great!  Cut 5 had a bit of an increase in time, but it turned out that cut was kind of a dummy.  Cut 5 took a random permutation of the non-negative integer variables and added a constraint Σ xi ≥ -1. This constraint clearly doesn’t do anything: CPLEX throws it away during preprocessing.

But look at Cut 10.  It decreased computation time by 33%.  It is amazing!  Cut 10 took a random permutation of the non-negative integer variables and added a constraint Σ xi ≥ -1. And that seems to work really well!

Hold on…. What’s going on here?  In fact, each of the cuts is simply a random permutation of the variables and a redundant constraint.  How can that have any effect?

CPLEX (as with Gurobi or any other solver) has a certain “randomness” in its operation.  This 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.  And, of course, the exact solution reported can then affect the branch and bound tree (since different variables might have fractional values).

If you change the internal ordering of the variables, you can change the operation of the branch and bound algorithm.  Adding the redundant cut changed the internal ordering of the variables, so the timing results could vary.   Not every instance has this aspect.  Some have relatively consistent computation time independent of the ordering.  But some instances vary a lot based on the ordering.

This is insight 1:  branch and bound timings may vary a lot due just to the random choices of the algorithm.

If your computation time is too long, try permuting the variables.  If 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.

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?  And how many good ideas have been discarded due to “bad luck” from the random number generator?

But this still leaves a puzzle:  almost every random ordering is better than default CPLEX.   Does this mean that you should at least randomly generate an variable ordering?  One gentleman at the conference, vibrating with excitement, thought he had the justification for this:

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.  This must be messing up CPLEX.  What a great insight!

That hyperventilating gentleman was me.  And Matteo quickly and firmly showed that I was wrong.  How could almost all of the orderings do better than default CPLEX?  Look back, the hint is there…..

 

 

 

How did we get our instances?  Let me quote myself:

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).

In doing this, he biased the sample!  Anything default CPLEX did well on (under 100 seconds), we threw out!  So the sample was made up of things that default CPLEX did not do well on.  It is no wonder that “Cut 1” had an advantage.  If 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”.  If you toss out instances that an algorithm works well on, don’t be surprised if it does poorly on the rest.

So this is insight 2:  if 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.

I can’t tell you the number of times I have read computational papers that make the bias mistake.  And I rarely noticed it.  I will now!

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

I cannot do full justice to Matteo’s talk:  there were many more insights and surprises.  The associated paper (with Michele Monaci) is here.  And if you get a chance to see him give the talk, do so!

After that talk, I will never look at computation in integer programming the same way again.  That presentation alone was worth the flight to Brazil!

Added 9/26:  Matteo has kindly provided his slides, which are available here.

 

Come work at Carnegie Mellon!

I teach (and, now, administrate) in the Tepper School of Business at Carnegie Mellon University.  Unlike most engineering-oriented universities, CMU does not have an Industrial (or Systems) Engineering department, so operations research people are scattered throughout the university.  The Tepper contingent is a big one (senior faculty include Balas, Cornuejols, and Hooker) and is augmented by others in the school with operations research interests (people like Sridhar Tayur who is in our operations management group).  But there are lots of OR people elsewhere, including Chemical Engineering (Ignacio Grossman, for instance), Mathematics (Alan Frieze), and Computer Science (Tuomas Sandholm).

The Heinz College of Public Policy and Information Systems has a large contingent of operations researchers, including Al Blumstein, one of the founding researchers in our field.  And the Heinz College is hiring in our area!  Here is the announcement:

Carnegie Mellon University’s Heinz College  is currently expanding its program targeted at analysis, design, and eventual implementation of Urban Systems and is seeking to recruit tenure-track faculty to be key participants in those developments. Heinz College (www.heinz.cmu.edu) consists of a School of Public Policy and Management and a School of Information Systems and Management.

We are seeking individuals from a diversity of related disciplines, including economics, transportation, operations research and the management sciences, statistics, and systems engineering with specific attention to civil engineering.

Our interests in Urban Systems include transportation systems, public-safety systems, and the built environment. While these problem domains are diverse, to be addressed effectively an interdisciplinary perspective is required. We are thus seeking candidates who are open to collaborating with researchers from other disciplines. We have developed relationships with a number of cities, including Pittsburgh and New York, as sources of data, experimental opportunities for improved system designs, and expertise in the realm of problems associated with their operating systems.

All candidates should have a PhD (or should demonstrate that one will be achieved shortly) in relation to one of the identified disciplines and have demonstrated research competence. Interested applicants are asked to send their application to the Urban Systems Search Committee at urban-sys-heinz-college@andrew.cmu.edu. An application should include a cover letter indicating their particular interests and their sense of fit with the Heinz College, a CV, copies of any published papers, and three sources of reference letters.

We will be conducting interviews at the October INFORMS meeting in Phoenix. For consideration at these meetings, applications should be submitted at least one month in advance.

If this sounds like you, please consider applying.  I look forward to having even more operations research on this campus!