University of Southampton’s game-changing algorithm for sports scheduling

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.