Sports timetabling at ITC2021
3rd of 13 teams · best known result on 16 of 45 instances
Task
Schedule a double round-robin tournament: every team meets every other twice, once at home. The 45 competition instances came in the RobinX format, with hard constraints that must hold and soft constraints whose weighted violations are minimized.
The constraints fall into five families: capacity (how often a team may play at home or away within a set of slots), game (matches forced or forbidden in given slots), breaks (two home or two away games in a row), fairness, and separation (a minimum gap between the two meetings of the same pair).
Approach
01Baseline: one monolithic MILP
A binary variable says whether team i hosts team j in slot s. The formulation is exact, but every break needs extra linearisation variables, so it only pays off on small instances without hard break or separation constraints.
02Patterns: breaks first
Breaks are the bottleneck, so they are solved separately. Stage one chooses home-away patterns that minimize breaks, subject to home-game counts and the hard capacity constraints. Stage two assigns each team one pattern, chosen from the stage-one solution and every pattern with at most one break, and then schedules the games.
03Mirrored: half the problem
Where the format allows it, the second half repeats the first with venues swapped. The model halves in size and separation constraints hold by construction; the price is a smaller feasible region and at least 3T − 6 breaks for T teams.
042-Phased: decompose by halves
Schedule the first half, then the second given the first. Limits that span both halves are split in proportion to the slots each half contains: a capacity limit of 2 over slots {0, 1, 20, 21} becomes a limit of 1 over {0, 1} and 1 over {20, 21}. A game forced into the second half fixes home and away and the allowed slots in the first.
This decomposition gave the best schedule on 22 of the 45 instances. A hybrid with the patterns stage covers instances where break penalties dominate.
05A portfolio, chosen per instance
For each instance, pick the formulations that suit the constraints it contains, run them, and keep the best schedule.
Result
Third place of thirteen teams, with the best or tied-best solution on 16 of the 45 instances.
Eight instances stayed without a feasible schedule; in seven of them the hard break constraints could not be met, which is where the work would continue.
The approach is published in the PATAT 2021 proceedings, volume II.