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!