El calendario de baloncesto de la Atlantic Coast Conference 1997-98 construido mediante programación entera

Las nueve escuelas de la Atlantic Coast Conference disputan cada enero y febrero un doble round robin de nueve semanas y 18 franjas, y el baloncesto era el mayor generador de ingresos de la liga: en 1995 la conferencia y sus universidades obtuvieron más de 30 millones de dólares de este deporte, casi todo procedente de derechos de televisión y radio más la taquilla. Hasta 1996-97 el calendario se elaboraba a mano en la oficina de la conferencia. Tras la incorporación de un noveno equipo (Florida State) en 1991-92 y la multiplicación de las peticiones televisivas, un intento de programación con restricciones para 1996-97 seguía produciendo un calendario con una separación deficiente entre enfrentamientos repetidos y necesidades televisivas no satisfechas.

Para 1997-98 la ACC recurrió a George Nemhauser y Michael Trick. Su sistema enumeró todos los patrones de temporada legales —8 como local, 8 como visitante, 2 descansos a lo largo de 18 franjas, como máximo dos partidos consecutivos como local o como visitante—, conservando 38 de 2.304 candidatos. Un programa entero ensambló conjuntos de nueve patrones (17 conjuntos, menos de un minuto cada uno), y un segundo IP de unos 300 variables generó los 826 calendarios factibles en menos de diez minutos, todo en una Sun SPARCstation 20 con CPLEX 4.0. Una enumeración final de 24 horas de asignaciones de equipo a patrón —aproximadamente 300 millones de opciones— dejó 17 calendarios factibles.

Estos se redujeron a tres y se presentaron; la ACC, consultando a ESPN y Raycom, adoptó uno como calendario oficial masculino, y un calendario femenino aceptado surgió del mismo sistema. Los requisitos más difíciles solo afloraron en el diálogo: ESPN quería Duke-North Carolina en la franja 10 y en el partido final, lo que descarta un calendario totalmente espejado, y Raycom tenía elaboradas preferencias para febrero. Nemhauser y Trick atribuyen al sistema su capacidad de respuesta en un día: la conferencia podía examinar calendarios reales y seguir refinando lo que realmente necesitaba.

Enumerar los patrones de local/visitante y luego elegir la temporada mediante programación entera

Dividir la temporada primero en un patrón L/V/D separa cómo es el año de un equipo de contra qué oponente se enfrenta, convirtiendo un problema enorme en tres pequeños.

La enumeración era barata a esta escala —2.304 patrones candidatos de los cuales 38 eran legales— mientras que la teoría de diseños combinatorios solo podía caracterizar unos pocos calendarios derivados a mano.

Aplazar la asignación de equipos reales a los patrones hasta el final permitió que la etapa de calendario ignorara las preferencias específicas de cada escuela, manteniendo los programas enteros pequeños y rápidos.

La restricción vinculante no fue la elegancia algorítmica sino la velocidad de respuesta: la ACC seguía añadiendo requisitos tardíos, y solo un sistema rápido como un día podía absorberlos.

Cuando las partes interesadas no pueden enunciar sus requisitos de antemano, unos calendarios candidatos rápidos les enseñan lo que realmente necesitan. La enumeración más la optimización estándar supera a esperar métodos elegantes.

El marco patrón-calendario-asignación se convirtió en la plantilla estándar para la programación de deportes de round robin en la literatura de investigación operativa. El episodio siguió siendo una referencia viva: un seguimiento de 2001 en Operations Research volvió a resolver la misma instancia de 1997-98 con programación con restricciones de dominio finito y reportó una aceleración drástica frente a la enumeración más programación entera. La lección más profunda —que la generación rápida de calendarios es una herramienta de negociación entre programadores, conferencias y emisoras— ha moldeado los proyectos de programación de ligas desde entonces.