Publication details

Saarland University Computer Science

Global Constraints for Round Robin Tournament Scheduling

Martin Henz, Tobias Müller, Sven Thiel

European Journal for Operational Research 153(1):92-101, February 2004

In the presence of side-constraints and optimization criteria, round robin tournament problems are hard combinatorial problems, commonly tackled with tree search and branch-and-bound optimization. Recent results indicate that constraint-based tree search has crucial advantages over integer programming-based tree search for this problem domain by exploiting global constraint propagation algorithms during search. In this paper, we analyze arc-consistent propagation algorithms for the global constraints all-different and one-factor in the domain of round robin tournaments. The best propagation algorithms allow us to compute all feasible perfectly mirrored pattern sets with minimal breaks for intermural tournaments of realistic size, and to improve known lower bounds for intramural tournaments balanced with respect to carry-over effects.

Download PDF        Show BibTeX               

Login to edit

Webmaster, Wed Sep 16 10:47:00 2009