*Scheduling Sport
Tournaments using Constraint Logic Programming* Andrea Schaerf
Many sport leagues (e.g. football,
hockey, basketball) face the problem of scheduling the matches of the national
championship, which is usually a round robin tournament.
In this work, we deal with the problem
of finding a schedule for a round robin tournament with various types of constraints,
including availability for matches and stadia. For example, a constraint can state that a
team must play not home in a given round, or a pair of teams cannot match at a given
round.
Constraints are split into hard
(requirements) and soft ones (wishes): Hard constraints must
necessarily be satisfied by the solution, soft ones instead are associated with a penalty,
and they contribute to the objective function to minimize.
We tackle the problem using a two-step
approach (as in [2]). The first step is the generation of a fixed tournament pattern ,
which is a tournament in which teams are replaced by numbers. This step can be done using
known graph-theoretic results [1]. The second step is the assignment of real teams to
distinct numbers in the pattern, and it involves the solution of a minimum-cost bipartite
graph matching with side constraints, which turns out to be an NP-complete problem.
The solution is based on a depth-first
branch and bound technique implemented in the constraint logic programming language
ECLiPSe (version 3.5.2) using the finite domain library.
The program is divided into three main
parts:
1. In the first phase, the program
builds the tournament pattern based on the number of teams, and it declares and
initializes all the auxiliary data structures, which are used for constant-time retrieval
of all the information related to the pattern.
2. In the second phase, each team is
associated with a finite domain variable, whose value
corresponds to the number assigned to the team in the tournament pattern. The domain of
all variables is initially set to the integer interval from 1 to the number of teams.
Constraints on the finite domain variables are stated based on the hard constraints of the
problem.
3. In the third phase, variables are
instantiated one at the time, and constraints are propagated over the domains of the non
instantiated variables. After a first solution is found, soft constraints are also taken
into account. They allow for pruning by calculating a lower bound of the objective
function for each partial solution, and comparing it against the objective value of the
current best solution. Backtracking occurs either because the domain of a variable becomes
empty or because the lower bound of the objective function exceeds the current best
solution.
For the constraints that cannot be
checked because the variables involved are not instantiated, the lower bound evaluation
relies on the computation of the minimum of their penalty ranging on the values in the
current domain of the variables.
The critical issues of our program (and
of constraint programming in general) are the ordering of the variables to be instantiated
and the ordering of the values for instantiation.
Regarding the former issue, we isolate
a small group of teams, called top teams, to be instantiated first, based on the type of
constraints stated on them. In particular, top teams are subject to constraints which
regulate the spreading of their mutual matches during the season.
For variable selection of regular
(non-top) teams, the program relies on the deleteffc built-in of ECLiPSe, that retrieves
the variable with the smallest domain and (in case of equal size) the most constrained
one.
Regarding the latter issue, the
selection is done based on the lower bound of the objective function for each possible
instantiation. Lower bounds are calculated all at once and are sorted in ascending order,
to be
selected one at a time upon backtracking.
The experimental results show that for
all practical setting of constraints, it takes at most 20 minutes to generate the optimal
solution. By setting artificial difficult situations, the computing time grows to about 1
hour.
For the same problem, the program
developed by Schreuder [2] runs in two minutes. However, he uses an incomplete heuristic
procedure, whereas we always find the optimal solution.
Whenever a faster result is needed, for
example if the constraints of the problem need to be modified
interactively, we employ two incomplete algorithms for quick near optimal solutions, which
can be
activated on demand. The first one is based on reducing the branching factor during the
search. That is, it does not consider all possible values for the selected variable, but
only the best k ones, where k is a selected parameter. For k=2 the program runs within 2
minutes and most of the times produces the optimal solution.
The other fast method is based on local
search: If there is a change in the constraints, after the optimal
solution was found, the algorithm is not rerun from scratch, but the solution is adjusted
based on local modifications (typically a series of swaps in the assignment of two teams).
**References**
[1] D. de Werra. Geography, games and
graphs. Discrete Applied Mathematics, 2:327-337, 1980.
[2] J. A. M. Schreuder. Combinatorial
aspects of construction of competition dutch professional football leagues. Discrete
Applied Mathematics, 35:301-312, 1992.
Dipartimento di Informatica e
Sistemistica
Universita di Roma "La
Sapienza"
Via Salaria 113, 00198 Roma, Italy
aschaerf@dis.uniroma1.it |