A traditional Benders’ approach to sports timetabling

Even for sports leagues with a small number of teams, the construction of a round-robin timetable taking into account various constraints, e.g., venue availability or travel distance, can be challenging. It is therefore common to decompose the problem with the first-break-then-schedule approach, which first decides when teams play home or away after which it determines a compatible assignment of opponents. When there are more time slots than games per team, so-called relaxed timetables, an alternative is the first-day-off-then-schedule approach which starts by deciding when teams receive a day of rest. Despite the popularity of these approaches, a major unsolved question is how to efficiently backtrack between the different phases of the algorithm. Moreover, existing backtracking schemes can only cope with a very limited set of timetable requirements. The main contribution of this paper is to show how traditional Benders’ decomposition relates to the aforementioned approaches, and how Benders’ cuts can be used to organize backtracking. To show the effectiveness and versatility of the proposed framework, we construct compact timetables that minimize the total number of travel trips, and relaxed timetables that either balance the games over the season or minimize the total differences in rest time of opposing teams. Furthermore, we discuss the quality of the obtained Benders’ cuts and strengthen integer programming formulations from the literature to construct relaxed round-robin timetables.