Almost 10 years ago, Kelly Easton, George Nemhauser and I created something called the Traveling Tournament Problem. The name is George’s: I wanted to call it the Problem where Teams Play a Round Robin and Travel and Stuff, but George’s name is catchier. The problem came from work we had done with Major League Baseball in creating their schedule. Rather than try to post 150 pages of requests and requirements (which MLB would never let us do anyway), we abstracted out the key aspects of the schedule. Those were:
- Travel: a wish to keep the total travel down, and
- Flow: a wish not to be home or away for more than 3 series consecutively.
I also added a “no repeat” constraint: if A is at B, then B cannot be at A in the next time slot.
When we put this together, we also put together the website http://mat.tepper.cmu.edu/TOURN to keep track of results and that turned out to be a great idea. By having one site with results and instances, it has been easy to keep track of “current records”.
When I first worked on this, my goal was to show how some of our methods that we use for MLB could handle problems of reasonable size for the Traveling Tournament Problem. That turned out to be impossible to do. The Traveling Tournament Problem is hard! Even solving the eight team problem turned out to be nontrivial. Six teams is doable with a bit of work.
Kelly Easton, in her dissertation, put a lot of effort into the TTP, and even solved the eight team problem. She used a network of 20 computers over the course of a week to prove optimality. Unfortunately, she did not include the “no repeat” constraint, so we didn’t have the result for exactly the right problem. While we believed that adding the “no repeat” constraint wouldn’t affect things too much, Kelly graduated, began working (for my small sports scheduling business) and we never solved the real problem.
Despite lots and lots of people working on the TTP, proving the optimality of a known solution to NL8 with value 39721 has been elusive. In fact, relatively little (but some, thanks to Melo, Ribeiro, and Urrutia) work has been done on improving lower bounds.
I was thrilled yesterday to get an email Stefan Irnich of Aachen who, together with his master student Ulrich Schrempp, claims to have proved the optimality of 39721. But here is when it gets hard. How do I know? It is easy to check feasible solutions, but unless there is a simply calculated lower bound, it it hard to confirm optimality. Fortunately Stefan sent the slides of his work, and it seems clear that the approach they are taking is one that would work, and would be stronger than what others have tried. So I have no hesitation in proclaiming that NL8 is now solved! I am sure there are easily dozens (OK, half-dozens … OK, a half-dozen) people who are excited about this, and I am one of them (and it is my blog).
On to NL10!
This is an issue that comes up whenever someone publishes that a solution has been proven optimal by branch and bound. B&B simply doesn’t provide any certificate of optimality in the same way that algorithms for LP and other convex optimization problems do.
In one embarrasing incident, a paper that I coauthored included an incorrect solution to a linear ordering problem- CPLEX claimed that the solution was optimal, but the objective value was a 5 digit integer, and a tolerance that I didn’t know CPLEX used needed to be set to a tighter than default value to get the correct optimal solution.
The best approaches to dealing with this that I know of are getting solutions from independent software and making the source code for the branch and bound solvers available so that others can review them.
Brian’s point is well taken, and is much more broadly relevant than just this context. With the increasing sophistication of software tools supporting theoretical mathematics–such as Maple and Mathematica–more and more published results are dependent on the output of software. To the extent that those outputs are too complex to verify by hand after the fact, our research is dependent on proprietary black-box systems that cannot be validated by the researchers or the community that is supposed to be able to reproduce them.
It is not enough for a referee or other researcher to use the same software with the same inputs to get the same result. If Joe takes Jill’s problem and Maple or CPLEX and gets the same result that Jill gets with Maple or CPLEX, that’s meaningless. Results need to be reproduced with alternative,independently developed systems. The best situation is to have the software source code available for inspection.
A sample of relevant links:
COIN-OR: open-source optimization codes (disclosure: I’m involved with COIN-OR).
SAGE: an open-source alternative to Maple, Mathematica, Matlab
Mathematical Programming Computation: a new journal that aims to publish reproducible computational optimization studies, including software
There are others worth searching for as well.
What kind of proof do you have to say that half-dozen is an upperbound 🙂 Thanks Michael.