🧩 Constraint Solving POTD:Sports League Scheduling

[github-actions[bot]]

Category: Scheduling · Date: 2026-04-10

---

Suppose you're tasked with building the fixture list for a professional football (soccer) league. Every club must play every other club exactly once at home and once away — but clubs also demand fairness: no team should play five away games in a row, rival clubs can't clash on the same weekend, and stadiums must be available on assigned dates. Welcome to Sports League Scheduling, one of the most commercially important and combinatorially rich problems in constraint solving.

---

Problem Statement

Double Round-Robin Tournament Scheduling (DRR)

Given n teams (assume n is even), schedule a season of 2(n−1) rounds such that:

1. Every team plays exactly one game per round.
2. Each ordered pair (i, j) with i ≠ j appears exactly once (team i hosts team j).
3. (Canonical constraint) No team plays more than P consecutive home games or more than P consecutive away games (typically P = 3).

Small concrete instance — 6 teams, 10 rounds:

Round	Game 1	Game 2	Game 3
1	1 vs 2	3 vs 4	5 vs 6
2	1 vs 3	2 vs 5	4 vs 6
...	...	...	...
10	6 vs 5	4 vs 3	2 vs 1

Input: number of teams n
Output: a full schedule matrix S[i][r] ∈ {1..n} where S[i][r] is the opponent of team i in round r, plus a home/away indicator H[i][r] ∈ {0,1}.

Variants add:

• Travel minimization (TTP — Traveling Tournament Problem): minimize total distance all teams travel during the season.
• Break minimization: a break is two consecutive home or two consecutive away games; minimize the total number of breaks.
• Venue/date constraints: some games must (or must not) happen on specific rounds.

---

Why It Matters

• Professional sports leagues (NFL, Premier League, NBA, La Liga) invest heavily in schedule optimization. A good schedule balances rest, travel fatigue, and broadcast appeal — affecting hundreds of millions of dollars in revenue.
• Olympic and tournament organization: multi-sport events like the FIFA World Cup group stage must satisfy fairness, venue sharing, and broadcast separation constraints simultaneously.
• Operations research benchmark: the Traveling Tournament Problem (TTP) is a canonical OR competition benchmark used to evaluate solver progress since 2001.

---

Modeling Approaches

Approach 1 — Constraint Programming (CP)

Decision variables:

opponent[i][r]  ∈ {1..n}   // opponent of team i in round r
home[i][r]      ∈ {0, 1}   // 1 = team i plays at home in round r
```

**Core constraints:**

```
// Each team plays exactly once per round
∀r: alldifferent( [opponent[i][r] | i = 1..n] )   -- actually 
    each team plays exactly one match, so opponent is a permutation

// Symmetry: if i plays j, then j plays i in the same round
∀i, r: opponent[ opponent[i][r] ][ r ] = i

// Home/away consistency: exactly one home, one away per game
∀i, r: home[i][r] + home[ opponent[i][r] ][ r ] = 1

// Each pair (i,j) meets exactly twice — once per direction
∀i≠j: |{r : opponent[i][r] = j ∧ home[i][r] = 1}| = 1

// No-repeat: i and j don't play consecutive rounds
∀i, r: opponent[i][r] ≠ opponent[i][r+1]

// Break limit: at most P consecutive home or away games
∀i: no sub-sequence of home[i][·] of length P+1 is all-0 or all-1
```

**Trade-offs:** CP handles the combinatorial structure naturally with powerful global constraints (`alldifferent`, sequence constraints). Propagation is strong, but the search space grows as `O(n!)` per round.

---

#### Approach 2 — Integer Programming (MIP/ILP)

**Decision variables:**

```
x[i][j][r] ∈ {0,1}   // 1 if team i hosts team j in round r
```

**Constraints:**

```
// Each pair (i,j) scheduled exactly once as home game
∀i≠j:   Σ_r  x[i][j][r] = 1

// Each team plays exactly one home and one away game per round
∀i, r:  Σ_j  x[i][j][r] = 1
         Σ_j  x[j][i][r] = 1

// No-repeat: i and j don't clash in consecutive rounds
∀i≠j, r:  x[i][j][r] + x[j][i][r] + x[i][j][r+1] + x[j][i][r+1] ≤ 1

// Break constraint: sum of home games over any window of P+1 rounds ≥ 1
∀i, r:  Σ_{k=r}^{r+P}  x[i][·][k]  ≥ 1   (and similar for away)

Objective (TTP): Minimize Σ_{i,r} dist[ i ][ S[i][r-1] → S[i][r] ]

Trade-offs: ILP benefits from LP relaxation bounds and mature branch-and-bound solvers (CPLEX, Gurobi). Variable count is O(n2 · rounds), which becomes large quickly, but LP relaxations provide tight lower bounds for TTP.

---

Approach 3 — Local Search / Metaheuristics

Start from a feasible round-robin schedule (easy to construct with a polygon construction) and iteratively swap games between rounds, using simulated annealing or tabu search to escape local optima.

Trade-offs: Cannot prove optimality but scales to n = 30+ teams where exact methods fail. The best known TTP solutions for n = 16 were found by metaheuristics, not exact solvers.

Example Model — MiniZinc (CP, break minimization)

int: n = 6;
int: rounds = 2*(n-1);

% opponent[i,r] = who team i plays in round r
array[1..n, 1..rounds] of var 1..n: opp;
% home[i,r] = 1 if team i is at home in round r
array[1..n, 1..rounds] of var 0..1: home;
% breaks[i,r] = 1 if team i has a break at round r (same H/A as r-1)
array[1..n, 2..rounds] of var 0..1: brk;

% Symmetry: games are mutual
constraint forall(i in 1..n, r in 1..rounds)(
  opp[opp[i,r], r] = i
);

% Exactly one home and one away per game
constraint forall(i in 1..n, r in 1..rounds)(
  home[i,r] + home[opp[i,r], r] = 1
);

% Each pair (i,j) plays exactly once with i at home
constraint forall(i in 1..n, j in 1..n where i != j)(
  sum(r in 1..rounds)(opp[i,r] = j /\ home[i,r] = 1) = 1
);

% No-repeat: teams don't meet in consecutive rounds
constraint forall(i in 1..n, r in 1..rounds-1)(
  opp[i,r] != opp[i,r+1]
);

% Count breaks
constraint forall(i in 1..n, r in 2..rounds)(
  brk[i,r] = bool2int(home[i,r] = home[i,r-1])
);

% Minimise total breaks
solve minimize sum(i in 1..n, r in 2..rounds)(brk[i,r]);
```

</details>

---

### Key Techniques

#### 1. Canonical Symmetry Breaking

A naive DRR model has enormous symmetry: you can permute team labels, rename rounds, or reflect the schedule without changing its quality. Standard symmetry-breaking fixes:

- **Team ordering:** Force `opponent[1][1] = 2` (pin team 1's first opponent).
- **Round equivalence:** Lexicographically order the game sets in the first half vs. second half.
- **Home/away reflection:** For team 1, fix `home[1][1] = 1`.

Symmetry breaking can reduce search space by a factor of `n! · 2^n` — dramatic for `n ≥ 8`.

#### 2. Global Sequence Constraints

The no-repeat and break-limit constraints are naturally expressed with the `sequence` global constraint:

```
sequence(min, max, q, x, S)  ←  in every window of q consecutive
                                  variables of x, at least min and
                                  at most max belong to set S

This enables efficient propagation with sliding window algorithms in O(n) rather than checking all windows naively in O(n·q).

3. Lower Bounds for TTP

For the Traveling Tournament Problem, the independent lower bound (ILB) technique builds a relaxation by solving a separate shortest-path problem for each team independently (ignoring inter-team constraints), then summing the results. This provides tight dual bounds used in branch-and-bound and guides local search neighborhoods. The ILB approach was a breakthrough that brought TTP closer to practical optimality.

---

Challenge Corner

The Balanced Scheduling Extension:
In many real leagues, the schedule is split into two halves: every team plays every other team once in the first half, then again in the second half — but with home/away roles reversed. This is called a mirrored DRR schedule.

🤔 Can you prove that a mirrored schedule always has at least n−2 breaks (for even n)? This is a known theoretical lower bound. Can you encode this lower bound as a constraint to tighten your model? What symmetry-breaking constraints are most effective for mirrored schedules compared to general DRR?

---

References

1. Rasmussen & Trick (2008). "Round Robin Scheduling — A Survey." European Journal of Operational Research 188(3): 617–636. Comprehensive survey of the field.
2. Easton, Nemhauser & Trick (2001). "The Traveling Tournament Problem: Description and Benchmarks." CP 2001, LNCS 2239. The paper that established TTP as a community benchmark.
3. Van Hentenryck & Vergados (2006). "Population-Based Simulated Annealing for the Traveling Tournament Problem." AAAI 2006. Best-known metaheuristic approach.
4. Rossi, van Beek & Walsh, eds. (2006). Handbook of Constraint Programming, Chapter 22 (Scheduling). Elsevier. Covers CP scheduling models including sports scheduling.

---

Next up: rotating to a topic we haven't yet visited — stay tuned! 🔔

Generated by Constraint Solving — Problem of the Day · ● 210.7K · ◷

• expires on Apr 17, 2026, 12:55 PM UTC

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #25806.