Argonne National Laboratory

Scheduling Double Round-Robin Tournaments with Divisional Play using Constraint Programming

TitleScheduling Double Round-Robin Tournaments with Divisional Play using Constraint Programming
Publication TypeJournal Article
Year of Publication2016
AuthorsCarlsson, M, Johansson, M, Larson, J
JournalEuropean Journal of Operational Research
Volume259
Issue3
Pagination1180-1190
Date Published06/2017
Other NumbersANL/MCS-P5524-0116
AbstractWe propose a tournament format that extends a traditional double round-robin format with divisional single round-robin tournaments. Elit- serien, the top Swedish handball league, uses such a format for its league schedule. We introduce a constraint programming model that characterizes the general double round-robin plus divisional single round-robin format. This integrated model allows scheduling to be performed in a single step, as opposed to common multi-step approaches that decompose scheduling into smaller problems and possibly miss optimal solutions. In addition to general constraints, we introduce Elitserien-specific requirements for its tournament. These general and league-specific constraints allow us to identify implicit and symmetry-breaking properties that reduce the time to solution from hours to seconds. A scalability study of the number of teams shows that our approach is reasonably fast for realistic league sizes. The experimental evaluation of the integrated approach takes considerably less computational effort to schedule Elitserien than does the previous decomposed approach.  
URLhttp://www.sciencedirect.com/science/article/pii/S0377221716309584
PDFhttp://www.mcs.anl.gov/papers/P5524-0116.pdf