K. Easton, G. Nemhauser, M. Trick, "Solving the Traveling Tournament Problem: A Combined Integer Programming and Constraint Programming Approach", E. Burke and P. Causmaeher (eds.), Springer Lecture notes in Computer Science 2740, 63-77, (2004).  [PDF]

The traveling tournament problem asks if there exists a competition schedule that allows teams in a league to play each other twice while minimizing travel distance.  This paper discusses algorithms that address this deceptively complex problem and presents a new solution for an eight-team league.

————–

Most domestic soccer competitions (and Champions League group stages) use the double round-robin format, and for most leagues, it is sufficient to have a schedule template, assign numbers to teams, and then pull numbers out of a bowl.  But what if you want to develop a schedule that minimizes the travel burden of all of the league teams and satisfies some other constraints as well?  It is this question that George Nemhauser and his research team has addressed over the past ten years, with results that have been directly applied to the major sports leagues.

George Nemhauser is a professor of Industrial and Systems Engineering at Georgia Tech (my undergraduate alma mater), and Kelly Easton is his former Ph.D. student.  Michael Trick is a professor and associate dean at Carnegie Mellon's School of Business, and together they have formed a company that performs scheduling for various sports leagues, primarily Major League Baseball and college athletics. 

The traveling tournament problem (TTP) is a sports version of the traveling salesman problem (TSP), which is a classic operations research problem.  (The basic traveling salesman problem is "Assuming a home city for a salesman and N cities to which the salesman wishes to travel, what is the path that allows the salesman to visit all of those cities once and minimize his distance traveled?")  The sports equivalent is this:

Given a set of N teams in a league, what is the schedule that allows each team to play all of the other teams twice (home and away) that does the following?

1. Minimize excessively long home stands or away trips
2. Minimize travel for all teams

The "home and away" requirement defines the feasibility element of the problem, while the numbered constraints define its optimality element.  TTP/TSPs are of great interest to the operations research community because of their applications to logistics, scheduling, and manufacturing (from construction to supply chain).  They are also used to benchmark the performance of certain computational algorithms. 

What is challenging about the traveling tournament problem (and the traveling salesman problem) is that while it is easy to state, it is extremely difficult to solve.  The TSP is considered to be an "NP-hard" problem, which is shorthand for "non-deterministic polynomial time hard", which in English means that the problem is infeasible and/or hard to solve in a short period of time except for some very simplified examples.  Moreover, it is hard to verify that the solution is actually the optimum one, again within a reasonable amount of time.  It is possible to devise an algorithm that gives a "close enough" solution, but that is not at all trivial.

For example, solutions that satisfy requirements (1) and (2) separately have been developed using integer programming and constraint programming, respectively.  You would think that a solution that satisfies requirements (1) and (2) would be just as easy to develop, but you would be wrong.  That Nemhauser and his group developed a TTP solution for an eight-team league was a really big deal in operations research circles when this paper was first presented.  These problems also take a very long time to solve — Nemhauser said that parallel computation was required to solve the scheduling problem for an eight-team league and the process still took four days!

I am still struggling to understand exactly what they did, but Nemhauser et al. developed a hybrid algorithm that combines constraint programming and integer programming into something called "branch-and-price".  Branch-and-price is a variation of branch-and-bound algorithms that evaluate solutions by using upper and lower bounds of variables to narrow the solution space, but in this case using linear programming to develop a measure of "price" — in this case, team travel.

The major conclusion from this work is that if scheduling an optimal double round-robin tournament for an eight-team league is so cost- and resource-prohibitive, I cannot imagine how much effort is required to develop an optimal schedule for a 18- or 20-team league.  It is at that point that one stops talking about "optimal" and starts talking about "close enough".  So perhaps we should hold on to the plastic balls and drawing bowls.  But for leagues that span a large geographic area, like Russia, China, or the USA, the TTP might become relevant to the competition committees.