Coarse-to-Fine Search for Traveling Tournaments at Any League Size

Scheduling a sports league so that teams travel as little as possible is a classic hard optimization problem. The traveling tournament problem asks for a double round-robin season (every pair of teams meets twice, once at each home) in which no team plays more than $k$ consecutive home or away games and no pair meets in back-to-back rounds, with the goal of minimizing total distance traveled. The best recent algorithms take the same first step: group nearby teams into small "super-teams" that travel together, using a minimum-weight matching or a packing of three-team paths. They then build a schedule for the super-teams and expand it into games between individual teams. These constructions set records and carry approximation guarantees. Each one works only for league sizes in one residue class (such as $n \equiv 0 \pmod 8$ or $n \equiv 4 \pmod 6$), and none has been tested beyond about 40 teams. The local-search methods that handle any $n$ make expensive moves and stall as leagues grow.

We propose to treat the super-team grouping as a coarsening step, the way multilevel graph partitioners shrink a graph, solve it, and refine it. The search first runs a penalty-based annealer on the small coarse problem of super-teams, where a move touches $n/2$ or $n/4$ entities instead of $n$. It then lifts the coarse schedule to individual teams and repairs it. The claim is that the geometric grouping is the part of the constructive algorithms that carries their quality, and that the rigid divisibility conditions do not. If that holds, coarse-to-fine search should match the special-purpose constructions where they apply. It should also produce comparable schedules at every league size, and its lead over flat annealing should widen as $n$ grows, which we measure with explicit scaling curves up to $n = 100$.

What the literature gives us, and what it leaves open

The constructive line of work supplies the grouping. Goerigk et al. cluster teams into nearby triplets by packing three-vertex paths. They show that such a packing weighs much less than two-thirds of an optimal Hamiltonian cycle, and they reach a record of 589,123 on NFL28, beating 609,788. Their schedule generation requires $n \equiv 4 \pmod 6$. Zhao and Xiao's TTP-2 algorithm pairs teams by minimum perfect matching into super-teams and proves a $1+O(1/n)$ ratio. It improves 15 of 16 benchmark instances by an average of 2.66%, but only when $n/2$ is odd. Their TTP-4 algorithm builds four-team super-teams from two matching edges, giving a $1.625+\epsilon$ ratio and a 6.65% average improvement over Westphal and Noparlik on 9 instances, restricted to $n \equiv 0 \pmod 8$. These papers motivate the proposal because they show the grouping matters. They also constrain it, because they show the closed-form expansion does not generalize. We reuse their groupings but drop their closed-form expansion.

The local-search line supplies the repair machinery. TTSA deliberately allows schedules that break the rules and charges a penalty for each violation, oscillating the penalty weights so the search can cross between isolated regions of valid schedules. Its large ejection-chain move has $O(n^3)$ size, and it pushed NL16 below 280,000. PBSA runs 80 annealing trajectories in waves, restarting most from the best solution while letting a few elite runs continue. It reduced optimality gaps by 27% on NLB-16, 45% on CIRC20, and 48% on NFL20. Both search over individual teams from unstructured starts. We run the same penalty-based search, but first on the coarse problem and then on the full problem.

A third relevant result is the linear-distance work. Hoshino and Kawarabayashi collapse geography onto a line and get schedules within 2.1–4.0% of optimal for the Japanese league. Zhao and Xiao's EPTAS gives $(1+\epsilon)$-approximations on lines but has an impractical constant and no experiments. This work matters to us in two ways. Line instances give a regime where we can compute lower bounds and check how much quality the coarsening loses. Its failure on non-linear geography is also the reason we do not reduce general instances to a line.

From the scalability direction, we take one specific lesson about summarization. Replacing many points by a few weighted representatives works when the summary preserves the objective, as with ε-kernel coresets and the Johnson–Lindenstrauss result for clustering, which preserves cost for every partition at once. We do not claim such a guarantee for tournaments. Our weaker analogue is an accounting: we measure how much travel the coarse problem's cost fails to capture, and how much of that the fine-level repair recovers.

Core Claim

Fix a grouping $\mathcal{G}$ of the $n$ teams into super-teams of size $s \in \{2, 3, 4\}$, taken from a minimum-weight matching or a three-path packing. When $n$ is not divisible by $s$, a few groups are allowed to be smaller. Let $C(\mathcal{G})$ be the best total travel among schedules in which members of each super-team make the same road trips, as far as the rules permit. The claim has three parts. First, $C(\mathcal{G})$ is within a few percent of the best known unrestricted result on standard instances. Second, an annealer working on $\mathcal{G}$ finds near-$C(\mathcal{G})$ schedules far faster than an annealer working on individual teams. Third, a short fine-level repair closes most of the remaining gap. The divisibility conditions become irrelevant because the coarse annealer never needs a closed-form expansion. It only needs a cost for lifting each coarse schedule to individual teams, and it accepts that the lift may break some rules, which the fine level then repairs.

Research Program

The coarse level is a double round-robin among super-teams. A coarse game between two super-teams expands into a fixed block of individual games across a short run of rounds, using the left, middle, and right super-game patterns of Zhao and Xiao where they fit and a small library of patterns for irregular group sizes. The coarse annealer uses TTSA-style moves, including swapping homes, rounds, and teams, plus a coarse version of the partial round swap, all applied to super-teams. Its objective is the expanded travel plus oscillating penalties for violations of the consecutive-games limit and the no-repeat rule after expansion. Because the coarse league has $n/s$ entities, the cubic ejection-chain neighborhood shrinks by about $s^3$. Most of the scaling benefit is expected to come from this reduction.

The fine level lifts the best coarse schedules to individual teams. It runs the full-resolution TTSA neighborhood, still with penalties, for a fixed short budget. Here it can break super-team cohesion wherever that saves distance. Two choices are studied rather than fixed in advance. One is when to lift: after convergence, or several times in a V-cycle (alternating coarse and fine passes) that re-forms groups from the current schedule's actual co-travel. The other is how to handle leftover teams when $n$ is not divisible by $s$: either as singleton super-teams or by cloning a nearby team as a zero-distance placeholder that is removed during repair.

The analysis tracks three gaps separately on every instance. The grouping gap compares $C(\mathcal{G})$, estimated by long coarse runs, against the best known unrestricted value. The search gap compares the coarse annealer's result against $C(\mathcal{G})$. The repair recovery is the fraction of the grouping gap that fine search wins back. This decomposition shows whether any failure comes from the grouping, the coarse search, or the lift.

Baselines

The naive reference point is TTSA run once from a random schedule on individual teams with the same total wall-clock budget as our method. It shows what penalty-based annealing achieves without structure. On NL14 and NL16 we check our reimplementation against the reported thresholds of below 200,000 and below 280,000 (TTSA).

The strongest search baseline is PBSA (Van Hentenryck and Vergados), because it is the best general-$n$ method in the file and the main competitor wherever no construction applies. The file reports its gains only as relative gap reductions (27% on NLB-16, 45% on CIRC20, 48% on NFL20), and I found no absolute PBSA distances on Lacuna. We therefore rerun it with the same number of cores, the same total CPU-hours, and the same tuning budget for temperatures and penalty schedules that our method receives. We also give our method a matched population of coarse trajectories, so any gain cannot be credited to parallelism.

The strongest constructive baselines, on the residue classes where they apply, are the TTP-2 matching algorithm (2.66% average improvement on 15 of 16 instances), the TTP-4 matching algorithm (6.65% average improvement over Westphal and Noparlik on 9 instances with $n \equiv 0 \pmod 8$, within 9.55 seconds), and the path-packing hybrid for $k=3$ (NFL28 = 589,123). We run each with its published local-search phase. On its own residue class, our method beats a construction only if it matches or improves the construction's distance at no more than ten times its runtime. On other residue classes, it succeeds if it stays within the same percentage of our best-known value as it does on the class where the construction applies.

The key ablation keeps everything identical, including the moves, penalties, budget, and fine-level repair, but replaces the geometric grouping $\mathcal{G}$ with a random grouping of the same sizes. If random groups perform about as well, the claim that geometry carries the quality fails, and any gain comes from coarsening alone. A second ablation removes the coarse level, starting fine search from a single lifted greedy coarse schedule, to isolate the value of searching at the coarse level.

Why not just…?

Why not just run PBSA or TTSA longer? This is the real threat. On instances of up to 20 teams, more parallel annealing may match anything we do. The case against it is about scaling. The ejection-chain move grows as $n^3$, and the papers report stagnation that motivated reheats and populations. No paper in the file reports either method beyond 40 teams. The scaling experiment below settles this. If flat PBSA's percentage gap to our method does not grow with $n$ at matched compute, the scaling claim is wrong and we will report that.

Why not just project onto a line and use the linear-distance algorithms? The 2.1–4.0% result of Hoshino and Kawarabayashi relies on the Japanese league already lying along a corridor. On a line, the distance between non-adjacent cities is the sum of every segment between them, which overstates travel on circular or planar layouts. The EPTAS lower bounds also hold only for exactly collinear distances. We include a line-projection baseline that projects onto the first principal axis, solves with the expander heuristic, and re-scores the schedule on true distances. We expect it to be competitive on NPB-like line instances and to lose on CIRC and Galaxy instances.

Why not just round $n$ to the nearest valid size and add a bye? This is the obvious patch for the divisibility conditions. The no-repeat and consecutive-games rules make it hard to remove rounds afterward, because one deletion cascades into many violations. That cascade is why TTSA searches through rule-breaking schedules in the first place. The padding-by-clones variant in our program is this patch made concrete. We compare it directly against the singleton-group variant, so if simple padding plus repair suffices, the experiment will show it.

Proposed Experiments

The instances are the Michael Trick benchmark set (NL4–16, CIRC, NFL20–32, Galaxy up to 40), the NPB distances, and synthetic families we generate. The synthetic families are CIRC$n$, uniform points in the plane, three-dimensional Galaxy-style point clouds, and points on a line, each at $n = 10$ to $100$ in steps of 2 so that every residue class modulo 4, 6, and 8 is covered. We test $k \in \{2, 3, 4\}$.

The metrics are total travel, the percentage gap to the best known value or to a per-team lower bound, and time to reach within 1% of the method's final value. The per-team lower bound is the sum, over teams, of each team's cheapest set of trips visiting all opponents with at most $k$ per trip. It is loose but available at every $n$. Line instances provide a tighter reference through bridge-crossing counting.

There are four decisive checks. The first is reproduction: on restricted residue classes, our method should come within 1% of the published constructions, for example NFL28 near 589,123. The second is the scaling curve: plot the percentage gap of flat PBSA relative to coarse-to-fine against $n$ at matched CPU-hours, and test whether it rises with $n$. The third is residue flatness: for each method, plot quality against $n \bmod 8$, where we predict flat curves for our method and sawtooth curves for the constructions' nearest-size variants. The fourth is the random-grouping ablation, which should lose clearly on geographic instances and lose little on CIRC, where all groupings of adjacent teams look alike.

The method fails as proposed if the grouping gap alone exceeds about 5% on NFL and Galaxy instances, or if flat PBSA at matched compute is no worse at $n = 100$ than at $n = 20$.