Scheduling sports tournaments by mixed-integer linear programming and a cluster pattern approach : computational implementation using data from the International timetabling competition 2021

Abstract

The International Timetabling Competition (ITC) has a long tradition of arranging scientific competitions within the research area of timetabling and its applications. The 2020-2021 edition is devoted to sports timetabling. The aim of ITC 2021 is to stimulate the development of solution approaches for the construction of round-robin timetables, meaning that each team plays every other team a fixed number of times. Each instance consists of a time-constrained double round-robin tournament. Further, the competition considers two types of constraints: hard constraints represent fundamental properties of the timetable that can never be violated, while soft constraints represent conditions that are desirable to satisfy. The resulting problem is to find a timetable the penalties from violated soft constraints. In this thesis, we present a heuristic solution approach using a combination of Mixed- Integer Linear Programming (MILP) and cluster patterns for generating timetables in sports tournaments. Further, we examine how our solution approach perform on 45 experimental problem instances presented in the ITC 2021. To the best of out knowledge, this is the first time a approach including clusters patterns, has been tested on an experimental database. The computational results show that our solution method is capable of generating a double round robin timetable for most of the data instances. Further, it provides better results in a shorter amount of time when compared to running the default MILP model.