Minimizing Breaks in Sport Scheduling with Local Search

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.