Der Basketball-Spielplan der Atlantic Coast Conference 1997-98, erstellt durch Integer Programming

Die neun Schulen der Atlantic Coast Conference spielen jeden Januar und Februar ein neunwöchiges Doppel-Rundenturnier mit 18 Slots, und Basketball war der größte Einnahmebringer der Liga: 1995 erzielten die Conference und ihre Universitäten über 30 Millionen Dollar aus dem Sport, fast alles aus TV- und Radiorechten sowie Eintrittsgeldern. Bis 1996-97 wurde der Spielplan im Conference-Büro von Hand erstellt. Nachdem 1991-92 ein neuntes Team (Florida State) beigetreten war und die Fernsehwünsche zunahmen, lieferte ein Constraint-Programming-Versuch für 1996-97 dennoch einen Spielplan mit schlechter Trennung von Wiederholungsspielen und unerfüllten TV-Anforderungen.

Für 1997-98 wandte sich die ACC an George Nemhauser und Michael Trick. Ihr System enumerierte jedes legale Saisonmuster – 8 Heimspiele, 8 Auswärtsspiele, 2 Freilose über 18 Slots, höchstens zwei aufeinanderfolgende Heim- oder Auswärtsspiele – und behielt 38 von 2.304 Kandidaten. Ein Integer Program stellte Neun-Muster-Sets zusammen (17 Sets, jeweils unter einer Minute), und ein zweites IP mit etwa 300 Variablen generierte alle 826 machbaren Spielpläne in unter zehn Minuten, alles auf einer Sun SPARCstation 20 mit CPLEX 4.0. Eine abschließende 24-stündige Enumeration der Zuordnung von Teams zu Mustern – rund 300 Millionen Optionen – ließ 17 machbare Spielpläne übrig.

Diese wurden auf drei reduziert und eingereicht; die ACC, die ESPN und Raycom konsultierte, übernahm einen als offiziellen Herren-Spielplan, und ein akzeptierter Damen-Spielplan stammte aus demselben System. Die schwierigsten Anforderungen tauchten erst im Dialog auf – ESPN wollte Duke-North Carolina in Slot 10 und im Finale, was einen vollständig gespiegelten Spielplan ausschließt, und Raycom hatte ausgefeilte Februar-Präferenzen. Nemhauser und Trick schreiben die Ein-Tages-Wende dem System zu: Die Conference konnte echte Spielpläne betrachten und das, was sie tatsächlich brauchte, weiter verfeinern.

Heim-/Auswärtsmuster enumerieren, dann die Saison per Integer Programming auswählen

Die Aufteilung der Saison in ein H/A/B-Muster trennt zunächst, wie das Jahr eines Teams aussieht, davon, auf welchen Gegner es trifft, und verwandelt ein einziges riesiges Problem in drei kleine.

Die Enumeration war bei dieser Größe günstig – 2.304 Kandidatenmuster, von denen 38 legal waren –, während die kombinatorische Designtheorie nur wenige handabgeleitete Spielpläne charakterisieren konnte.

Die Zuweisung realer Teams zu Mustern bis zum Ende aufzuschieben erlaubte es der Spielplanstufe, schulspezifische Präferenzen zu ignorieren, wodurch die Integer Programs klein und schnell blieben.

Die bindende Einschränkung war nicht algorithmische Eleganz, sondern die Geschwindigkeit der Umsetzung: Die ACC fügte laufend späte Anforderungen hinzu, und nur ein tageschnelles System konnte sie aufnehmen.

Wenn Stakeholder ihre Anforderungen nicht im Voraus formulieren können, lehren sie schnelle Kandidaten-Spielpläne, was sie tatsächlich brauchen. Enumeration plus Standardoptimierung schlägt das Warten auf elegante Methoden.

Das Rahmenwerk aus Muster, Spielplan und Zuweisung wurde zur Standardvorlage für die Spielplanung von Rundenturnieren im Sport in der OR-Literatur. Die Episode blieb ein lebendiger Benchmark: Eine Nachfolgearbeit in Operations Research von 2001 löste dieselbe Instanz von 1997-98 mit Constraint Programming über endliche Domänen erneut und berichtete von einer dramatischen Beschleunigung gegenüber Enumeration plus Integer Programming. Die tiefere Lehre – dass schnelle Spielplangenerierung ein Verhandlungswerkzeug zwischen Spielplanern, Conferences und Rundfunkanstalten ist – hat seither Projekte zur Liga-Spielplanung geprägt.