Scheduling sport tournaments using constraint logic programming
We tackle the problem of scheduling the matches of a round robin tournament for a sport league. We formally define the problem, state its computational complexity, and present a solution algorithm using a two-step approach. The first step is the creation of a tournament pattern and is based on known graph-theoretic results. The second one is a constraint-based depth-first branch and bound procedure that assigns actual teams to numbers in the pattern. The procedure is implemented using the finite domain library of the constraint logic programming language eclipse. Experimental results show that, in practical cases, the optimal solution can be found in reasonable time, despite the fact that the problem is NP-complete.
|Problem Solving, Control Methods, and Search (acm I.2.8), Nonnumerical Algorithms and Problems (acm F.2.2), Combinatorics (acm G.2.1)|
|Logic programming (msc 68N17), Searching and sorting (msc 68P10), Analysis of algorithms and problem complexity (msc 68Q25), Problem solving (heuristics, search strategies, etc.) (msc 68T20)|
|CWI. Probability, Networks and Algorithms [PNA]|
Schaerf, A. (1997). Scheduling sport tournaments using constraint logic programming. CWI. Probability, Networks and Algorithms [PNA]. CWI.