{"id":293,"date":"2008-06-25T14:53:48","date_gmt":"2008-06-25T18:53:48","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=293"},"modified":"2008-06-25T14:53:48","modified_gmt":"2008-06-25T18:53:48","slug":"nl8-solved","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2008\/06\/25\/nl8-solved\/","title":{"rendered":"NL8 Solved!"},"content":{"rendered":"

Almost 10 years ago, Kelly Easton, George\u00a0 Nemhauser and I created something called the Traveling Tournament Problem<\/a>.\u00a0 The name is George’s:\u00a0 I wanted to call it the Problem where Teams Play a Round Robin and Travel and Stuff, but George’s name is catchier.\u00a0 The problem came from work we had done with Major League Baseball in creating their schedule.\u00a0 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.\u00a0 Those were:<\/p>\n

    \n
  1. Travel:\u00a0 a wish to keep the total travel down, and<\/li>\n
  2. Flow: a wish not to be home or away for more than 3 series consecutively.<\/li>\n<\/ol>\n

    I also added a “no repeat” constraint:\u00a0 if A is at B, then B cannot be at A in the next time slot.<\/p>\n

    When we put this together, we also put together the website http:\/\/mat.tepper.cmu.edu\/TOURN<\/a> to keep track of results and that turned out to be a great idea.\u00a0 By having one site with results and instances, it has been easy to keep track of “current records”.<\/p>\n

    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.\u00a0 That turned out to be impossible to do.\u00a0 The Traveling Tournament Problem is hard!\u00a0 Even solving the eight team problem turned out to be nontrivial.\u00a0 Six teams is doable with a bit of work.<\/p>\n

    Kelly Easton, in her dissertation, put a lot of effort into the TTP, and even solved the eight team problem.\u00a0 She used a network of 20 computers over the course of a week to prove optimality.\u00a0 Unfortunately, she did not include the “no repeat” constraint, so we didn’t have the result for exactly the right problem.\u00a0 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.<\/p>\n

    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.\u00a0 In fact, relatively little (but some, thanks to Melo, Ribeiro, and Urrutia) work has been done on improving lower bounds.<\/p>\n

    I was thrilled yesterday to get an email Stefan Irnich<\/a> of Aachen who, together with his master student Ulrich Schrempp, claims to have proved the optimality of 39721.\u00a0 But here is when it gets hard.\u00a0 How do I know?\u00a0 It is easy to check feasible solutions, but unless there is a simply calculated lower bound, it it hard to confirm optimality.\u00a0\u00a0 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.\u00a0 So I have no hesitation in proclaiming that NL8 is now solved!\u00a0 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).<\/p>\n

    On to NL10!<\/p>\n","protected":false},"excerpt":{"rendered":"

    Almost 10 years ago, Kelly Easton, George\u00a0 Nemhauser and I created something called the Traveling Tournament Problem.\u00a0 The name is George’s:\u00a0 I wanted to call it the Problem where Teams Play a Round Robin and Travel and Stuff, but George’s name is catchier.\u00a0 The problem came from work we had done with Major League Baseball … Continue reading “NL8 Solved!”<\/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":[46,51],"tags":[],"class_list":["post-293","post","type-post","status-publish","format-standard","hentry","category-research","category-sports"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/293","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=293"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/293\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=293"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=293"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=293"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}