El Fixture del campeonato nacional de futbol está a cargo del Departamento de Ingeniería Industrial desde el 2005, después de que en 2004 los ingresos que genera el campeonato, se vieran muy afectados por poner el superclásico (Universidad de Chile vs Colo Colo) en la segunda fecha con un método aleatorio.
Este problema puede parecer simple, pero tiene un sin fin de alternativas: el numero de calendarios diferentes con un numero par de equipos jugando crece exponencialmente:
– Con 2 equipos se tiene solo 1 calendario.
– Con 4 equipos se tienen 6 posibles calendarios.
– Con 6 equipos se tienen 720 posibles calendarios.
– Con 8 equipos se tienen 31449600 posibles calendarios.
– Con 10 equipos se tienen 444733651353600 posibles calendarios.
– Con 12 equipos se tienen 10070314878246926155776000 posibles calendarios.
– Con 14 equipos se tienen 614972203951464612786852376432607232000 posibles calendarios.
etc. El campeonato tenía en ese entonces 20 equipos jugando, por lo que a pesar de lo que digan algunos, hacer un fixture si tiene mucha ciencia.
El modelo incluye restricciones sobre los partidos de local y visita, restricciones geograficas, partidos de local y visita frente a equipos grandes, que cada clasico entre la cato, el colo y la u se juega uno de local y el otro de visita, que ningun equipo juega dos veces seguidas con un equipo grande, que los partidos entre equipos grandes son en ciertas fechas, sobre la cantidad de partidos en Santiago, sobre partidos en zonas turisticas, sobre disponibilidad de estadios, restricciones de competencias internacionales y alternancia de localidad-visita entre torneos diferentes. Para lo anterior el modelo utiliza 8000 variables binarias y 3000 restricciones, se dejó corriendo más de un día y no se encontraron soluciones, por lo que se utilizaron patrones cercanos a la solución deseada para disminuir el tiempo de procesamiento. Con ello el tiempo de procesamiento se bajó a 10 minutos.
Finalmente se generan 70 calendarios por campeonato, los ejecutivos de la ANFP analizan 10 para decidir cual se usa.
Más información en el siguiente documento.