Generating a diverse and challenging set of sports timetabling problem instances

The fifth International Timetabling Competition (ITC2021) was held to instigate further research on automated sports timetabling. Its artificial problem instances require constructing a compact double round-robin tournament with 16 to 20 teams while respecting various hard constraints and minimizing the penalties from violated soft constraints. We discuss how we generated a set of challenging, diverse, and realistic problem instances for this timetabling competition. In particular, we present a set of features describing the structure of the problem instances, construct the so-called two-dimensional (2D) instance space of problem instances from the literature, and derive the region in instance space where all real-world-like instances are located. To generate a diverse and feasible set of problem instances, we propose the use of an instance generator whose parameters are set by an integer programming approach such that the resulting instance is projected at a specific spot in the 2D space. Finally, we learn about strengths and weaknesses of the algorithms developed by the participants, by drawing their so-called footprints on the instance space