I have always felt strongly that operations research needs more libraries of instances for various problem classes, along with listings of current best solutions. \u00a0By tracking how well we solve problems over time, we can show how we advance as a field. \u00a0It also makes it easier to evaluate new work, making both authors and referees work easier.<\/p>\n
I began this direction almost two decades ago when I spent a year at DIMACS<\/a> (a fantastic research institute on discrete mathematics and computer science based at Rutgers) when I (together with David Johnson) ran their Computational Challenge, with an emphasis on solving graph coloring, clique, and satisfiability instances. \u00a0From that, I put together a page on graph coloring<\/a> (which has to be one of the oldest pages on the internets!) \u00a0 David, Anuj Mehrotra and I followed that up in 2003 with an updated challenge<\/a> just on graph coloring. \u00a0 It was great to see people re-use the same instances, so we could understand the advances in the field. \u00a0It is hard to tell exactly how many papers have used the various benchmark repositories, but it is clearly the basis for hundreds of papers, based on google scholar hits on the DIMACS paper referencing the instances.<\/p>\n I had this experience in mind ten years ago when Kelly Easton, George Nemhauser and I wanted to publish about work we had done with Major League Baseball in their scheduling. \u00a0It made no sense to use MLB as a benchmark, since there is only one instance per year and much of the information about the needs of a schedule is confidential. \u00a0So we created the Traveling Tournament Problem<\/a> that abstracts two key issues in MLB scheduling: travel distance, and “flow” (the need to mix home and away games). \u00a0We created a set of instances, solving a few smaller ones, and let it loose on the world. \u00a0The result was fantastic: \u00a0dozens of groups started working on the problem, and we could clearly see which techniques worked and which didn’t.<\/p>\n I had made a terrible mistake when creating benchmarks for graph coloring. \u00a0I didn’t keep track of best results. \u00a0This led to a fair amount of chaos in the field, with contradictory results appearing (claimed coloring values better than claimed lower bounds), and no clear picture of where things are going. \u00a0I had thought at one time that I would try to clean things up with a “Repository of Optimization Instances and Solutions”<\/a>, but too many other things have intruded for me to spend the time necessary on that. \u00a0Fortunately, Stefano Gualandi and Marco Chiarandini have put together a site for graph coloring solutions,<\/a> and I hope they will be successful in their efforts to put a little structure in the field.<\/p>\n I learned from that mistake and was much more diligent about keeping track of solutions for the Traveling Tournament Problem. \u00a0The TTP site<\/a> is always up to date (OK, almost always), so people can reasonably trust the results there. \u00a0I have recently extended the site to include instances for non-round-robin scheduling<\/a> and for the Relaxed TTP<\/a> (where there is an opportunity for off-days).<\/p>\n One relatively new problem I am excited about is scheduling umpires in sports. \u00a0Former doctoral students Hakan Yildiz<\/a> (now at Michigan State) and Tallys Yunes<\/a> (Miami) and I developed a problem called the Traveling Umpire Problem which again tried to abstract out key issues in Major League Baseball scheduling. \u00a0In this case, the umpires want to travel relatively short distances (unlike the players, the umpires have no “home city”, so they are always traveling) but should not see the same teams too often. \u00a0This problem feels easier than the Traveling Tournament Problem, but we still cannot solve instances with 14 or more umpires to optimality. \u00a0This work received a fair amount of interest<\/a> when the university PR people caught hold of our Interfaces<\/em> paper<\/a>. \u00a0Since that paper, Hakan and I have put together a couple of other papers, exploring optimization-based genetic algorithms<\/a> and benders-based local search approaches for this problem (to appear in Naval Research Logistics). \u00a0Both papers illustrate nice ways of using optimization together with heuristic approaches. \u00a0The website for the problem<\/a> gives more information on the problem, along with instances and our best solutions.<\/p>\n I don’t think my repositories of benchmarks will be as influential as, say\u00a0MIPLIB<\/a>, which focuses on mixed integer programs. \u00a0But I do like to think that they make the operations research world run a bit smoother.<\/p>\n","protected":false},"excerpt":{"rendered":" I have always felt strongly that operations research needs more libraries of instances for various problem classes, along with listings of current best solutions. \u00a0By tracking how well we solve problems over time, we can show how we advance as a field. \u00a0It also makes it easier to evaluate new work, making both authors and … Continue reading “Benchmarks: Coloring, Sports and Umpires”<\/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":[10,12,51],"tags":[],"class_list":["post-1542","post","type-post","status-publish","format-standard","hentry","category-challenges","category-computing","category-sports"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1542","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=1542"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1542\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1542"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1542"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1542"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}