Eighteen teams. Thirty-four matchdays. Three hundred and six games. Each club plays every other club once at home and once away. Anyone who thinks planning a Bundesliga season cannot be difficult is mistaken, says Sven Krumke.
The mathematics professor is one of the few people in Germany who fully understands the intricacies of match scheduling. Together with his postdoctoral researcher at the time, Stefan Westphal, Krumke developed a mathematical system for optimising match schedules at the University of Kaiserslautern (now RPTU). This system forms the basis of the software solution that the German Football League (DFL) has been using ever since.
“Of course, you can generate a standard schedule by arranging the teams once and then rotating the matchups,” Krumke explains. “But that’s not what professional football is about. We do not want just any schedule, but a particularly beautiful one.”
With 18 teams, there are more than 10⁸¹ possibilities for the first four match days alone. That is more than there are atoms in the universe."
Sven Krumke
Here, “beautiful” means that the sequence of matches must meet a wide variety of requirements, which makes the process considerably more complicated. Some conditions are set in stone, such as each team playing only once on a given matchday, while others are “desired”. For example, a team should ideally alternate between home and away games. With 18 teams, however, this cannot work, which brings us to the first sticking point.
“We have conflicting goals,” Krumke explains, outlining the challenge. 'We want the highest possible attendance, but at the same time, there should be few breaks as possible in the rotation between home and away games.” Security issues also play a role. “Simultaneous home games for Dortmund and Schalke cause logistical problems for the police in North Rhine-Westphalia.” Finally, there is the dramatic arc to consider. Depending on how the season unfolds, the schedule should allow for a big stage towards the end of the season for relegation battles and high-stake matches. The DFL must weigh such factors, and this affects the entire system.
Anyone who talks to Krumke quickly realises that his heart beats for 1. FC Kaiserslautern. “Once it has got you, it just will not let you go, ” says the season ticket holder in the West Stand of the Fritz-Walter-Stadion.
“With the topic of schedule optimisation, we’re essentially bringing university research together with the West Stand. This is the perfect example of our area of expertise.” He is referring to discrete optimisation problems, which are mathematical models in which there are no intermediate values, only clear decisions: yes or no. “A team does not play against another team 93 per cent of the time, either or it does not.”
To demonstrate how mathematics addresses such problems, Krumke outlines the fundamental task of match scheduling: “There are n teams. Each team has n − 1 opponents because it plays against each one exactly once, but not against itself, and n(n − 1)/2 matches must be distributed so that each team plays exactly once per match day. The goal is to find a way to distribute the matches across the match days.”
“The schedule is not something you can just fill in; it is a combinatorial problem. Anyone who thinks they can simply try out all the possibilities will quickly hit a wall. With 18 teams, there are more than 10⁸¹ possibilities for the first four match days alone. That is more than there are atoms in the universe." Or, to put it simply for anyone who is overwhelmed by such numbers: “There are an awful lot of possibilities. Completely crazy,” says Krumke.
Krumke and his colleague Westphal managed to make the enormous mountain of possible combinations more manageable through mathematical modelling. “We formulated the match scheduling as an integer linear program. This is a mathematical model that works with yes-no decisions. It includes variables for every possible team combination, as well as for constraints and exclusions. It also includes objective functions that evaluate how “good” a schedule is, for example in terms of spectator interest or the distribution of home and away games.”
“The schedule is not something you can just fill in; it is a combinatorial problem. Anyone who thinks they can simply try out all the possibilities will quickly hit a wall."
Sven Krumke
Geometrically, this results in a high-dimensional polyhedron — a solution space defined by many hyperplanes. “Each variable forms its own dimension within it. Every integer point within it represents a possible schedule. The optimisation process searches this space systematically for the best solution,” explains the professor. Based on this model, Stefan Westphal developed commercial software that was acquired by the DFL and has been in use there for over 15 years.
“In the very early days, the schedule was created heuristically, i.e. by trial and error. Swap, move, try,” says Krumke. But the days of manual 'tweaking', as he calls it, are long gone. Computer programs were already in use before the “Kaiserslautern solution”. “But the software in our system now enables the DFL to navigate the full spectrum of options, tweak individual parameters and generate schedules that work reliably within the bigger picture.”
“If FCK plays away twice in a row, I know we have made the unavoidable home-and-away mistake. It makes sense for the bigger picture. As a fan, though, I still think, “What a shame”, laughs Krumke.
Even though the topic is not new, the Bundesliga schedule remains a perennial favourite for the mathematicians at RPTU — but it is by no means their only research subject through which they can demonstrate that mathematics does not just take place behind closed doors.
“At ADAC, for example, there is a similar fundamental problem. Every breakdown must be attended to exactly once, and sequences, time windows and scarce resources must be planned as effectively as possible,” says Krumke, whose research group also works on school timetabling and rail transport logistics. The group is currently working on behalf of the Rhineland-Palatinate Ministry of the Interior to plan emergency medical service locations and shift systems. “These are all cases where the following applies: Mathematics can make a difference in the world.”
Here you'll find further reading:
S. O. Krumke, H. N. Noltemeier, „Graphentheoretische Konzepte und Algorithmen“, B.G. Teubner 2012
S. O. Krumke, E. Schmidt, and M. Streicher, „Robust Multicovers with Budgeted Uncertainty“, European Journal of Operational Research, Volume 274, Issue 3, May 2019, Pages 845-857
S. M. Dimant, and S. O. Krumke, „On Approximating Partial Scenario Set Cover“, Theoretical Computer Science, Volume 1023, January 2025.
