How OR is used to schedule sports competitions is a growing area of
research. From designing competitive football leagues to scheduling
basketball tournaments, creating optimal schedules requires intricate
decision-making and OR can make a valuable contribution.
Imagine creating a schedule for a league with 18 teams. Each team
needs to play every other team both at home and away, but that's just
the tip of the iceberg as there may be other challenges to consider
including:
- Venue availability: Stadiums might not be available as they are booked for concerts or maintenance.
- Travel considerations: Minimising fatigue for teams playing across vast distances.
- Team fairness: Ensuring no team has an unfair advantage in terms of home/away games or overall difficulty.
These are just a few examples, and the number of constraints can quickly multiply.
The University of Southampton's triumph at ITC2021
As sports scheduling is a relatively ‘young’ area of OR, without a
great deal of research, it became the focus of the ITC2021 competition.
The organisers’ goal was to broaden research around sports scheduling
and algorithms and learn from the research.
This global competition challenged participants to develop algorithms
for creating optimal schedules for double round-robin tournaments, a
common format in many sports leagues that is particularly applicable to
sports such as football.
A team from the University of Southampton, comprised of Professor
Toni Martínez-Sykora, Professor Chris Potts, and Doctor Carlos
Lamas-Fernández, decided to enter the competition. Their innovative
approach tackled the complexities of real-world scheduling constraints.
Decoding the Complexities: ITC2021 Constraints
The ITC2021 competition focused on creating time-constrained, double
round-robin tournaments for 18 to 22 teams. While the specific sport
wasn't defined, it resembled a football league structure. The real
challenge wasn't just fulfilling these basic requirements, but working
to a strict set of rules categorised into eight constraint groups:
- Capacity constraints These managed the number of
games teams played within a specific timeframe, ensuring fairness in
terms of home/away games and avoiding congested schedules for any team.
- Game constraints These dictated the required or
forbidden number of games played within a timeframe, accommodating
broadcaster demands or ensuring a minimum number of top team matchups
per week.
- Break constraints: These limited the number of
consecutive games with the same home/away status for a team, preventing
fatigue due to long stretches of away games.
- Fairness constraints: These ensured a level playing
field by managing the distribution of home games, limiting the maximum
difference between any two teams.
- Separation constraints (SE): These mandated a
minimum number of time slots between consecutive games involving the
same teams, guaranteeing sufficient rest between matchups.
To determine the scores, the contestants had to meet a number of hard
constraints and as many ‘soft’ constraints as possible in order to
minimise penalties.
The University of Southampton's algorithm addressed these intricate
constraints by combining techniques like Mixed-Integer Linear
Programming (MILP) for optimisation, pattern recognition for breaking
down the tournament into manageable phases, and a fix-and-optimise
heuristic for continuous improvement. As a result, the team had the
highest scores and won.
The University of Southampton's victory at ITC2021 highlighted the
growing importance of OR in sports scheduling. As leagues become more
complex and global, OR provides the tools to create balanced, efficient,
and engaging schedules.