by Mats Carlsson
To create a fair timetable for the men's handball league is a much more complex task than you would think. There are actually many more ways to do it than there are atoms in the universe, and only one of them is perfect. The trick is to find it!
The top Swedish men's handball league, Elitserien, consists of two divisions of seven teams each. Every season, a timetable for 33 periods needs to be constructed. In the first seven periods, two parallel tournaments are played with every team meeting every other team from the same division. In the next 13 periods, one league-level tournament is played with every team meeting every other team. In the last 13 periods, the league-level tournament is played again, in reverse order.
The timetable must satisfy a number of other rules, such as:
- If team A plays team B at home, then team B must play team A at home the next time they meet.
- Teams can play at home at most twice in a row and away at most twice in a row, and such cases should be minimized.
- Both divisions must have three pairs of complementary schedules.
- Specific high-profile matches between given teams should be scheduled in specific periods.
- Some teams can't play at home during specific periods, because the venue is unavailable.
Visually, you can think of it as a matrix with 280 cells, each filled with a number between 1 and 27. There are more than 10400 ways to do the task, or commonly expressed 1 followed by 400 zeroes. As a comparison there are only about 1080 atoms in the universe. Out of the vanishingly small amount of correctly filled matrices that you will find, there is one optimal solution. The trick is to find it.
Traditionally, the time-tabling has been carried out manually by the Swedish Handball Federation. The problem is too difficult for a human to solve to optimality, and so the Federation has always had to compromise and break some rules in order to come up with an acceptable timetable. The method from SICS solves it without breaking any rules.
Researchers at KTH, the Royal Institute of Technology, had a first attempt at the problem. They conducted an initial formal study of the Elitserien schedule problem, and discovered some important structural properties. SICS continued the study, formally modelled the problem using Constraint Programming, and was thereby able to solve it to optimality in about five CPU seconds.
They first defined the variables to be used in the CP set-up, and then the essential constraints to ensure the resultant schedule will satisfy Elitserien’s structural requirements. Next they highlighted some implied constraints and symmetry breaking properties that they found would greatly reduce the search effort. Finally, they modelled the league’s seasonal constraints so they could construct the entire schedule in an integrated approach. The constraint model was encoded in MiniZinc 1.6 and executed with Gecode 3.7.0 as back-end.
This timetabling problem is a typical combinatorial problem. Constraint programming has been used for sports scheduling before. However, case studies solved by integrated CP approaches are scarce in the literature. Perhaps the problems have been assumed to be intractable without decomposition into simpler sub-problems.
References:
[1] J Larson, M Johansson, M Carlsson: “An Integrated Constraint Programming Approach to Scheduling Sports Leagues with Divisional and Round-Robin Tournaments”, CPAIOR, LNCS 8451, pp. 144-158, Springer, 2014
[2] J. Larson, M. Johansson: “Constructing schedules for sports leagues with divisional and round-robin tournaments”, Journal of Quantitative Analysis in Sports (2014), DOI:10.1515/jqas-2013-0090
Please contact:
Mats Carlsson, SICS Swedish ICT, Sweden
E-mail:
