Generating Approximate Solutions to the TTP using a Linear Distance Relaxation

Richard Hoshino, Ken-ichi KawarabayashiJAIR 2012 · DOI

Introduction: The Traveling Tournament Problem

The Traveling Tournament Problem (TTP) is a classic challenge in sports scheduling that combines the combinatorial complexity of the Traveling Salesman Problem with the rigid constraints of a double round-robin tournament. The goal is to minimize the total distance traveled by all teams while adhering to three primary constraints:

  1. Each-venue: Every pair of teams must play twice, once at each team's home stadium.
  2. At-most-three: No team can play more than three consecutive home games or three consecutive away games.
  3. No-repeat: A team cannot play the same opponent in two consecutive games.

Due to these constraints, the TTP is "strongly NP-hard." Finding optimal solutions for even small leagues (e.g., 16 teams) can take days or weeks using traditional integer programming. This paper proposes a novel approach to generate high-quality approximate solutions rapidly by simplifying the underlying geography.

Methods: The Linear Distance Relaxation

The core innovation of this research is the Linear Distance Relaxation (LD-TTP). Instead of considering teams scattered across a 2D map with an $n \times n$ distance matrix, the authors assume all teams are located along a single straight line. This reduces the problem's complexity from $O(n^2)$ distance parameters to just $n-1$ variables representing the distances between adjacent teams on the line.

To apply this to real-world scenarios where teams are not naturally aligned, the authors use a Line-of-Best-Fit Heuristic. They project the actual geographic coordinates of the teams onto a single line that minimizes the sum of squared distances from the original points.

Figure 1: Projecting team locations onto a line of best fit to simplify the distance matrix.

Beyond the heuristic projection, the paper employs two main algorithmic strategies:

  • Optimal Enumeration for Small $n$: For leagues of 4 and 6 teams, the authors use combinatorial analysis to identify every possible optimal schedule under the linear assumption.
  • Expander Construction: For larger leagues (specifically $n \equiv 4 \pmod 6$), they developed a novel "expander" algorithm. This construction transforms a single round-robin schedule into a double round-robin schedule while maximizing "three-game road trips" between nearby teams to minimize travel.

Key Results and Benchmarks

The LD-TTP approach was tested against several standard benchmarks, including the National League (NL), Super Rugby (SUPER), and synthetic sets like GALAXY (3D stars) and CIRC (teams in a circle).

One of the most significant findings is that the linear relaxation often yields the exact optimal schedule for non-linear benchmarks. For instance, the technique found the distance-optimal tournament for all five standard 6-team benchmark sets (NL6, SUPER6, GALAXY6, CIRC6, CON6).

Figure 5: An optimal LD-TTP schedule for $n=4$ teams over 6 rounds. Bold entries indicate away games.

The "expander construction" provides a theoretical $4/3$-approximation ratio for the LD-TTP, which is significantly tighter than the best-known general TTP approximation of $5/3 + \epsilon$. In practice, the performance is even better; for 10 and 16-team leagues, the optimality gap was as low as 2.1% (CONS16) and 7.2% (GALAXY10). Furthermore, the speedup is dramatic: the LD-TTP approach solved the notoriously difficult "CIRC6" benchmark in just 0.3 seconds, a task that took state-of-the-art branch-and-price heuristics three hours.

Insights and Future Directions

The primary insight of this work is the "Linear Power": the optimal schedule for a linear league is frequently identical to the optimal schedule for a complex, non-linear league. By drastically reducing the search space through linear relaxation, researchers can find near-optimal solutions in a fraction of the time.

Future work includes extending the expander construction to league sizes where $n \equiv 0$ or $n \equiv 2 \pmod 6$ and exploring the application of linear relaxation to bipartite tournaments. While a small optimality gap (~2.3%) was observed for $n=6$, determining the maximum possible gap for larger $n$ remains an open theoretical challenge.

Summary updated

BibTeX
@article{hoshino2012generating,
  author = {Richard Hoshino and Ken-ichi Kawarabayashi},
  title = {{Generating Approximate Solutions to the TTP using a Linear Distance Relaxation}},
  journal = {J. Artif. Intell. Res.},
  year = {2012},
  doi = {10.1613/jair.3713},
}
Figure