Pascal van Hentenryck and Yannis Vergados
Sport scheduling has received significant attention in the recent years and has contributed many challenging applications for optimization technologies. This paper reconsiders the problem of minimizing the number of breaks in round-robin tournaments, an application which has been recently tackled by sophisticated constraint and mathematical programming approaches. It proposes a simulated annealing algorithm that finds optimal solutions very quickly for the largest instances available. On the larger instances (e.g., 28 teams), the algorithm is several orders of magnitude faster than earlier approaches. In addition, the experimental results indicate that near-optimal solutions can be obtained within 10 seconds for large instances. Of particular interest is the simplicity of the implementation, its automatic tuning of the parameters, and the fact that simulated annealing is an effective technique for another sport-scheduling application.