Kombinatorische Explosion beim FuĂźball
Die Erstellung des Bundesliga-Spielplans ist so komplex, dass reine Rechenleistung nicht reicht. Es braucht auch Fantasie, Kreativität und Erfahrung.
Am 14. August beginnt die neue Saison der Fußball-Bundesliga. Für den Spielplan gibt es mehr Möglichkeiten als Teilchen im Universum. Stephan Westphal hat eine Software geschrieben, die trotzdem eine fast optimale Lösung findet. Das berichtet das Magazin Technology Review in seiner aktuellen Ausgabe 8/2015 (jetzt am Kiosk oder im heise Shop zu bestellen).
Westphal, 38, ist Professor an der TU Clausthal in der Arbeitsgruppe "Diskrete Optimierung“. Er hat in Kaiserslautern über Online-Routenplanung und Maschineneinsatzplanung promoviert und danach als Berater für ein Unternehmen gearbeitet, das mathematische Optimierungssoftware herstellt. Einer der Kunden war die Deutsche Fußball Liga (DFL). So kam er in Kontakt mit der Sportbranche. Seitdem berät Westphal die DFL, die Basketball-Bundesliga und die Deutsche Eishockey Liga bei der Spielplangestaltung.
Bereits, wenn man den Spielplan der Fußball-Bundesliga des letzten Jahres nimmt und die Mannschaften darin vertauscht, ergeben sich 18! Möglichkeiten (6,4 x 1015). Dazu kommen noch zahlreiche Nebenbedingungen: In den Stadien sollen zum Beispiel auch Rockkonzerte und andere Veranstaltungen stattfinden. Zudem gibt es benachbarte Mannschaften, die nicht gleichzeitig zu Hause spielen sollten. Außerdem sollte der Aufsteiger nicht gleich zu Beginn dreimal hintereinander gegen starke Mannschaften spielen müssen. "Wenn man sich jetzt noch ein bisschen mehr Mühe gibt und weitere Optionen hinzuzieht, kommt man ruckzuck auf eine Größe von 1080“, sagt Westphal.
"Ganzzahlige lineare Optimierung“
Um unter diesen ganzen Optionen einen Spielplan zu finden, der möglichst viele der Anforderungen erfüllt, hat Westphal das Problem in ein Gleichungssystem mit ungefähr zehntausend Variablen umformuliert. Es lässt sich – theoretisch – mit der den Methoden der sogenannten "ganzzahligen linearen Optimierung“ lösen. "Aber das funktioniert in der Regel nicht, weil Probleme dieser Art für die Standardverfahren schlicht zu schwer sind“, sagt Westphal. "Wir haben diesen Effekt, den wir kombinatorische Explosion nennen. Mit mehr Optionen steigt die Rechenzeit exponentiell.“
Um die Rechenzeit zu reduzieren, hat er bestimmte Lösungsräume von vornherein ausgeschlossen. "Wenn eine Mannschaft zum Beispiel an zwei aufeinanderfolgenden Spieltagen ein Heimspiel hat, muss es eine andere Mannschaft geben, die an genau diesen beiden Tagen ein Auswärtsspiel hat“, so Westphal „Ich habe mir also darüber Gedanken gemacht, welche von diesen Heim-Auswärts-Mustern überhaupt zusammenpassen. Es ist wie bei einem Riesen-Heuhaufen mit einer Nadel drin: Ich zerschneide den Heuhaufen und sage dem Rechner: Pass mal auf, in der linken Hälfte kann nichts sein, da brauchst du gar nicht erst zu suchen.“ Für solche Tricks brauche man, so Westphal, "gesunden Menschenverstand, Fantasie, ein bisschen Kreativität und Erfahrung“.
Annäherung an perfekten Plan
Die Software läuft auf einem handelsüblichen Laptop und liefert nach einer überschaubaren Rechenzeit die ersten brauchbaren Pläne, die dann noch nachjustiert werden können – etwa um mit einem besonders tollen Eröffnungsspiel oder einem gelungenen Saisonabschluss eine gewisse Dramaturgie oder Emotionalität einzubringen.
Einen perfekten Plan wird es aber nie geben: "Fast alle Mannschaften haben zum Beispiel zwei Heim- oder zwei Auswärtsspiele nacheinander“, sagt Westphal. "So etwas lässt sich nicht vermeiden, das kann man auch beweisen.“ Auch im verbliebenen Lösungsraum nähert sich der Algorithmus einer optimalen Lösung allenfalls an. Immerhin kann die Software beispielsweise präzise angeben, dass eine gefundene Lösung nur noch 0,3 Prozent von der Bestmöglichen entfernt ist. (grh)
