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.