🔢 mathematics

Centralized Round-Robin Tournament Scheduling with a Flexible Number of Matches per Round

This paper addresses the NP-hard problem of minimizing total travel distance in centralized single round-robin tournaments with flexible match counts per round by establishing theoretical complexity results and polynomially solvable cases, while proposing a highly effective iterated local search heuristic that outperforms mixed-integer programming on large-scale instances.

Original authors: Hikaru Anai, Yunjian Cao, Wei Wu

Published 2026-10-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Hikaru Anai, Yunjian Cao, Wei Wu

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where the logistics of a sports league are not just about who plays whom, but about the journey itself. In the realm of operations research, a field dedicated to making complex systems run efficiently, researchers often tackle the puzzle of scheduling. A classic version of this puzzle is the round-robin tournament, a format where every team plays every other team exactly once. Traditionally, these tournaments are rigid: a round is a fixed block of time where the maximum number of possible games happens simultaneously, like a full house at a theater where every seat is filled. The challenge usually lies in deciding the order of these rounds or where to hold them to save time and money. But in the real world, particularly in regional amateur leagues and school sports in Japan, the rules are often more fluid. Organizers might not have enough fields for everyone to play at once, or they might want to limit travel for a specific group of teams on a given day. This flexibility means a single round could contain just one game, or ten, depending on what makes sense for that day. The question then becomes: how do you organize a season where the number of games per day can change, and every day has a single host location, to keep the total distance traveled by all teams as low as possible?

This is the specific problem a team of researchers from Shizuoka University and Seikei University set out to solve. They focused on a scenario where a central organizer picks one venue for an entire day, and then decides how many matches to schedule there, ensuring no team plays twice in that same day. Their goal was simple but difficult to achieve: minimize the total miles driven by all the teams to get to their games. To understand the difficulty, one must realize that every time you split a group of games into a new day, you might be able to pick a venue closer to those specific teams, but you also use up one of the limited days available in the season. It is a delicate balancing act between keeping the schedule compact and keeping the travel short.

The researchers first asked a fundamental question: is this problem solvable by a computer in a reasonable amount of time, or is it too chaotic to ever find the perfect answer? They proved that for the general case, the problem is computationally intractable. In plain terms, this means that as the number of teams grows, the time required to find the absolute best schedule explodes, making it impossible for even the most powerful computers to solve it perfectly for large groups. They demonstrated this by showing that even if you simplify the travel costs to just three possible values, the underlying logic remains too complex to crack efficiently. This finding is crucial because it tells tournament organizers that they cannot rely on a simple formula to get the perfect schedule for a large league; they will need smart shortcuts.

However, the study did not stop at proving the difficulty. The team discovered that under certain specific conditions, the problem becomes much easier. If the number of days available for the tournament is exactly the minimum required to fit all the games, the solution is straightforward and can be found quickly. They also identified a special case involving only two possible venues. In this scenario, they developed a method based on the mathematical structure of the teams' preferences to determine the best schedule instantly. This provides a powerful tool for smaller leagues or those with very limited venue options, allowing them to find the perfect schedule without needing a supercomputer.

For the more common and difficult situations involving many teams and many days, the researchers designed a sophisticated search strategy called an iterated local search. Think of this as a methodical way of exploring a vast landscape of possible schedules. The process starts with a decent schedule and then repeatedly tries to improve it by making small, strategic changes. These changes include merging two days of games into one and then splitting them back up differently, or moving a single game from one day to another to resolve a conflict. The algorithm is designed to escape local traps—situations where a schedule looks good but is actually far from the best possible—by occasionally making a larger, more disruptive change to shake things up and explore new possibilities.

When the researchers tested their methods on sixty-four different scenarios, ranging from eight teams to sixty-four teams, the results were striking. For smaller tournaments with fewer than thirty-two teams, their mathematical models could find the perfect schedule and prove it was the best possible. For the larger, more complex tournaments, the exact mathematical models often struggled, running out of memory or failing to find a solution within the time limit. In contrast, the new search strategy consistently found high-quality schedules. On the medium-sized problems, it produced solutions that were within a fraction of a percent of the theoretical best. Even on the largest problems where the exact models failed, the search strategy provided feasible schedules that were far superior to what the standard mathematical approaches could manage.

The study also revealed interesting insights into how the flexibility of the schedule affects the outcome. Having more available days to play games generally allows for better travel savings, but the benefit diminishes after a certain point. Similarly, having more venues to choose from helps reduce travel distance, but it also makes the scheduling puzzle harder to solve. The researchers found that by splitting the games across more days, organizers can group teams that live near each other and send them to a nearby venue, significantly cutting down on travel. This confirms that the flexibility to vary the number of games per day is not just a logistical convenience but a powerful lever for reducing costs and effort.

Ultimately, this work provides a complete toolkit for organizing these flexible tournaments. It offers a proof of the problem's difficulty, a set of exact solutions for special cases, and a robust, fast heuristic for the real-world scenarios that matter most. By combining deep mathematical theory with practical algorithm design, the researchers have given sports organizers a way to navigate the complex trade-offs between time, space, and travel, ensuring that the focus remains on the game rather than the journey.

Technical Summary: Centralized Round-Robin Tournament Scheduling with a Flexible Number of Matches per Round

Problem Definition

The paper addresses the Centralized Round-Robin Tournament Scheduling Problem with Flexible Matches per Round (CRRTSP-FMR). This problem arises in the context of regional amateur sports and school club leagues in Japan, where operational constraints often dictate that all matches within a specific round (time period) must be held at a single common venue.

Unlike traditional round-robin scheduling where each round is a fixed maximum matching (determined by the number of teams), CRRTSP-FMR allows the number of matches per round to be a decision variable. The scheduler must:

Assign every pair of $n$ teams to play exactly once.
Partition these matches into at most $q$ rounds (where $q \ge \rho(n)$ , the theoretical minimum number of rounds).
Assign a single common venue to each active round.
Ensure each team plays at most once per round.

The objective is to minimize the total travel distance from all teams to their assigned venues. The flexibility in the number of matches per round introduces a trade-off: splitting rounds allows the scheduler to select venues closer to specific subsets of teams, but it increases the total number of rounds required, potentially conflicting with the upper bound $q$ .

Methodology

1. Mathematical Formulations

The authors propose two Mixed-Integer Programming (MIP) models:

Time-Indexed Formulation: Explicitly indexes candidate rounds $k \in \{1, \dots, q\}$ . It uses binary variables for match-round assignment and venue-round assignment. To address symmetry (where the order of rounds does not affect the cost), the authors introduce symmetry-breaking constraints that enforce a canonical ordering based on the lexicographically smallest match index in each round.
Assignment-Based Formulation: Treats matches as jobs and "venue-use pairs" $(j, k)$ as machines. This formulation directly assigns matches to specific venue usages. It also incorporates symmetry-breaking constraints to order the uses of each venue based on the smallest match index assigned to them. The authors argue this formulation offers a stronger linear programming (LP) relaxation due to its packing structure.

2. Complexity Analysis

NP-Completeness: The decision version of CRRTSP-FMR is proven to be strongly NP-complete, even when travel costs are restricted to the set $\{0, 1, 3\}$ . The proof utilizes a reduction from the 3-edge-coloring problem of cubic graphs.
Polynomially Solvable Cases:
- Minimum Rounds ( $q = \rho(n)$ ): If the number of rounds equals the theoretical minimum, the problem is solvable in polynomial time. The optimal strategy involves assigning all rounds to the single venue minimizing total team travel.
- Lower Bound Attainability: The authors define an "independent-match lower bound" ( $Z_{LB}$ ) where every match is played at its cheapest possible venue. They prove that if the round limit $q$ is greater than or equal to the sum of the chromatic indices of the graphs formed by matches assigned to each venue, $Z_{LB}$ is attainable.
- Two-Venue Case ( $m=2$ ): For two venues, the problem reduces to analyzing two complementary threshold graphs. The authors develop an exact polynomial-time test ( $O(n \log n)$ ) to determine if the lower bound is attainable by computing the chromatic indices of these threshold graphs.

3. Heuristic Approach (Iterated Local Search)

For larger instances where exact methods fail, the authors propose an Iterated Local Search (ILS) heuristic:

Initial Solution: Generated via two methods: (1) 1-factorization with greedy splitting, and (2) Constructive edge coloring (Misra–Gries algorithm) followed by Kempe-chain packing to reduce rounds to $q$ .
Local Search Neighborhoods: The algorithm employs a best-improvement strategy using four neighborhoods:
1. Merge-and-Split: Merges two rounds and repartitions the matches into two new feasible rounds (modeled as a 2-coloring of a conflict graph).
2. Simple Ejection Chain: Moves a match to a new round, ejecting a conflicting match, which is then moved to a third round.
3. Variable-Depth Ejection Chain (VEC): Extends the simple chain with a beam-search to explore longer displacement sequences.
4. Eject-and-Inject: Removes an entire round, reassigns its matches, and creates a new round from a seed match to maintain the round count.
Perturbation (Kick Move): To escape local optima, a hybrid adaptive kick move is used. It randomly selects a subset of rounds, pools their matches, and reconstructs them. If reconstruction fails, a generalized Kempe chain shift is applied to permute matches among the selected rounds while preserving feasibility.

Computational Results

Experiments were conducted on 64 benchmark instances with $n \in \{8, 16, 32, 64\}$ teams, $m \in \{2, 4, 8, 16\}$ venues, and varying round limits $q$ .

MIP Performance:
- The Assignment-Based (AB) formulation significantly outperformed the Time-Indexed (TI) formulation on small to medium instances ( $n \le 32$ ), often proving optimality.
- However, both formulations struggled with $n=64$ . The AB model frequently encountered memory limitations or failed to find feasible solutions, while the TI model produced large optimality gaps.
- Symmetry-breaking constraints improved TI performance for $n=32$ but degraded AB performance on difficult instances.
ILS Performance:
- The ILS heuristic successfully found feasible solutions for all 64 instances.
- For $n=8$ and $n=16$ , the ILS matched proven optima (0% gap).
- For $n=32$ , the best configuration (using Merge-and-Split, Simple Ejection Chain, and Variable-Depth Ejection Chain) achieved an average optimality gap of 0.15%.
- For $n=64$ , the ILS maintained moderate gaps (average ~10.5% relative to the weak lower bounds of the MIP models), substantially outperforming the MIP approaches which often failed to produce feasible solutions.
- The "Eject-and-Inject" neighborhood was found to be counterproductive under the tested parameters, increasing average gaps.

Significance and Claims

The paper claims four primary contributions:

Problem Formulation: It introduces a novel scheduling variant (CRRTSP-FMR) that relaxes the fixed-round structure of classical round-robin problems, reflecting practical constraints in amateur sports.
Complexity: It establishes the intrinsic computational hardness of the problem (strongly NP-complete) even with simplified cost structures.
Structural Insights: It identifies polynomially solvable regimes and provides an exact optimality test for the two-venue case using threshold graph theory, characterizing when the independent-match lower bound is attainable.
Algorithmic Solution: It demonstrates that a tailored ILS heuristic, leveraging graph-theoretic constructs like edge coloring and Kempe chains, can effectively solve large-scale instances where exact MIP approaches fail.

The authors conclude that the flexibility in the number of matches per round allows for significant travel distance reductions by enabling venue selection closer to specific team subsets, provided the round limit $q$ is sufficiently high. They note that future work could incorporate additional real-world constraints such as venue availability, referee assignments, and fairness metrics.