Le calendrier de basket-ball de l'Atlantic Coast Conference 1997-98 construit par programmation en nombres entiers

Les neuf écoles de l'Atlantic Coast Conference disputent chaque janvier et février un double championnat aller-retour de neuf semaines et 18 créneaux, et le basket-ball était la plus grande source de revenus de la ligue : en 1995, la conférence et ses universités ont tiré plus de 30 millions de dollars de ce sport, presque entièrement des droits de télévision et de radio ainsi que des recettes de billetterie. Jusqu'en 1996-97, le calendrier était établi à la main au bureau de la conférence. Après l'arrivée d'une neuvième équipe (Florida State) en 1991-92 et la multiplication des demandes de télévision, une tentative de programmation par contraintes pour 1996-97 a tout de même produit un calendrier avec une mauvaise séparation des rencontres répétées et des besoins télévisuels non satisfaits.

Pour 1997-98, l'ACC s'est tournée vers George Nemhauser et Michael Trick. Leur système énumérait tous les motifs de saison légaux - 8 matchs à domicile, 8 à l'extérieur, 2 exemptions sur 18 créneaux, au plus deux matchs consécutifs à domicile ou à l'extérieur - en retenant 38 des 2 304 candidats. Un programme en nombres entiers assemblait des ensembles de neuf motifs (17 ensembles, en moins d'une minute chacun), et un second programme en nombres entiers d'environ 300 variables générait les 826 calendriers réalisables en moins de dix minutes, le tout sur une station Sun SPARCstation 20 avec CPLEX 4.0. Une énumération finale de 24 heures des affectations équipe-motif - environ 300 millions d'options - a laissé 17 calendriers réalisables.

Ceux-ci ont été réduits à trois et soumis ; l'ACC, en consultation avec ESPN et Raycom, en a adopté un comme calendrier officiel masculin, et un calendrier féminin accepté est issu du même système. Les exigences les plus difficiles n'ont émergé qu'au fil du dialogue - ESPN voulait Duke-North Carolina au créneau 10 et en finale, ce qui exclut un calendrier entièrement symétrique, et Raycom avait des préférences élaborées pour février. Nemhauser et Trick attribuent au système son délai d'exécution d'un jour : la conférence pouvait examiner de vrais calendriers et continuer à affiner ce dont elle avait réellement besoin.

Énumérer les motifs domicile/extérieur, puis choisir la saison par programmation en nombres entiers

Décomposer la saison en un motif D/E/B sépare d'abord l'allure de l'année d'une équipe de l'identité de ses adversaires, transformant un problème énorme en trois petits.

L'énumération était peu coûteuse à cette taille — 2 304 motifs candidats dont 38 légaux — tandis que la théorie des plans combinatoires ne pouvait caractériser que quelques calendriers dérivés à la main.

Reporter l'affectation des équipes réelles aux motifs jusqu'à la fin permettait à l'étape du calendrier d'ignorer les préférences propres aux écoles, gardant les programmes en nombres entiers petits et rapides.

La contrainte déterminante n'était pas l'élégance algorithmique mais la rapidité d'exécution : l'ACC ajoutait sans cesse des exigences tardives, et seul un système rapide à l'échelle d'un jour pouvait les absorber.

Lorsque les parties prenantes ne peuvent pas énoncer leurs exigences à l'avance, des calendriers candidats rapides leur apprennent ce dont elles ont réellement besoin. L'énumération combinée à une optimisation standard l'emporte sur l'attente de méthodes élégantes.

Le cadre motif-calendrier-affectation est devenu le modèle standard pour la planification des calendriers sportifs en round-robin dans la littérature de recherche opérationnelle. L'épisode est resté une référence vivante : une suite publiée en 2001 dans Operations Research a résolu à nouveau la même instance de 1997-98 avec la programmation par contraintes à domaines finis et a rapporté une accélération spectaculaire par rapport à l'énumération combinée à la programmation en nombres entiers. La leçon plus profonde - qu'une génération rapide de calendriers est un outil de négociation entre planificateurs, conférences et diffuseurs - a façonné les projets de planification de ligue depuis.