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