Which algorithm to select in sports timetabling?
David Van Bulck Dries Goossens Jan-Patrick Clarner Angelos Dimitsas George H. G. Fonseca Carlos Lamas-Fernandez Martin Mariusz Lester Jaap Pedersen Antony E. Phillips Roberto Maria Rosati
Any sports competition needs a timetable, specifying when and where teams
meet each other. The recent International Timetabling Competition (ITC2021) on
sports timetabling showed that, although it is possible to develop general
algorithms, the performance of each algorithm varies considerably over the
problem instances. This paper provides an instance space analysis for sports
timetabling, resulting in powerful insights into the strengths and weaknesses
of eight state-of-the-art algorithms. Based on machine learning techniques, we
propose an algorithm selection system that predicts which algorithm is likely
to perform best when given the characteristics of a sports timetabling problem
instance. Furthermore, we identify which characteristics are important in
making that prediction, providing insights in the performance of the
algorithms, and suggestions to further improve them. Finally, we assess the
empirical hardness of the instances. Our results are based on large
computational experiments involving about 50 years of CPU time on more than 500
newly generated problem instances.