Sports Tournament Scheduling

Sports tournament scheduling involves creating timetables for round-robin tournaments where each team plays every other team a fixed number of times. The problem becomes highly complex when considering real-world constraints such as venue capacity, travel considerations, and fairness requirements.

Problem Description

In sports timetabling, a round-robin tournament is a tournament where each team plays against every other team a fixed number of times; see [1]. Round-robin tournaments are very common in practice, especially double round-robin tournaments, where teams meet twice. Here, we consider such double round-robin tournaments with an even number of teams and with a time-constrained timetable. Under this setting, the total number of time slots is exactly equal to the total number of games per team, and hence each team plays exactly one game per time slot. In addition to these base constraints, each tournament has its own requirements such that real-life problems face very diverse constraints.

The instances contained in this benchmark repository are taken from [3] and [4] (corresponding author David Van Bulck ) and follow the XML-based human readable RobinX format; see [2]. The instances consider the following constraint types:

Constraints

1. Capacity Constraints (CA)

Regulate when teams can play home or away. There are four specific types of capacity constraints:

• CA1 : Team i plays at least or no more than k home games during specified time slots.
• CA2 : Same as CA1 but considering opponents as well.
• CA3 : No more than two consecutive home or two consecutive away games.
• CA4 : Same as CA2, but considering multiple teams.

2. Break Constraints (BR)

A team has a break if it plays consecutively at home or away. There are two specific types of break constraints:

• BR1 : Team i has no more than k breaks during specified time slots.
• BR2 : The number of breaks over all teams is no more than k .

3. Game Constraints (GA)

Game constraints enforce or forbid specific assignments of games to time slots:

• GA1 : No more than k games from a given list during specified time slots.

4. Fairness and Separation Constraints (FA, SE)

Increase the attractiveness and fairness of the tournament.

• FA1 : at any point in time, the difference in the number of home games played between any two teams does not exceed two.
• SE1 : there are at least 10 time slots between each pair of games involving the same teams.

Feasibility vs. Optimization Problem

In the original RobinX format, constraints can be either hard or soft. While hard constraints represent fundamental properties of the timetable and can never be violated, soft constraints rather represent preferences that should be satisfied whenever possible. In order to lower the entrance barrier, the quantum benchmark ignores all soft constraints which reduces the problem to a feasibility problem. A subset of the original instances were selected for which existing solvers could not find any feasible solution within a reasonable amount of time (see Large instances and [4]). Since the original instances are possibly bigger (16 to 20 teams; >100 variables), we also provide instances with 8 (see Small instances ) and 12 teams (see Medium instances ). For the original problem instances with soft constraints, see the ITC2021 instances .

Objective

For the feasibility version of the problem considered in this benchmark, the objective is to find feasible solutions to all instances in as little time as possible.

For the original ITC2021 problem, the objective is to minimize soft constraint violations. Please, refer to the competition manual for more information. If you find new best known solutions, please submit them to the official ITC2021 website .