Pablo Colombo
Pablo Colombo
Pablo Colombo
Fecha de Presentacion
Julio de 2015
2
Indice general
1. Introduccion 9
1.1. Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.1. Caso Testigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2. Existencia de un fixture con sistema Grand-Prix . . . . . . . . . . . . . . . 10
1.3. Fixture con sistema Grand-Prix de distancia mnima . . . . . . . . . . . . . 14
1.4. Resumen de la tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4. Multiplicacion de fixtures 35
4.1. Combinacion de m fixtures para n equipos. . . . . . . . . . . . . . . . . . . 36
4.1.1. Separacion de equipos y fechas en grupos . . . . . . . . . . . . . . . 36
4.1.2. Cuadrados Latinos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.3. Armado de los grupos de fechas . . . . . . . . . . . . . . . . . . . . . 38
4.1.4. Desarmado de partidos rally . . . . . . . . . . . . . . . . . . . . . . . 39
4.1.5. Verificacion de factibilidad . . . . . . . . . . . . . . . . . . . . . . . . 41
4.1.6. Propiedades del fixture construido . . . . . . . . . . . . . . . . . . . 42
4.2. Consecuencias del teorema de multiplicacion de fixtures . . . . . . . . . . . 43
3
4 INDICE GENERAL
Abstract
In this work we focus in indoor sports with tournaments that have an odd amount of
teams where each pair of teams play with each other four times, each team playing two
home matches. Let n be the total amount of teams. Two games are held each weekend, for
example, on a friday and a sunday. For each weekend, the n teams are separated into (n3)
2
couples and three teams are taken aside. Each couple plays two matches, one of these is
home team in both matches. The remaining threesome has one local team who plays to
the other two, one on friday and the other one on sunday. Each weekend every team plays
one or two matches, it is necessary to play for 2n weekends to complete the tournament.
The goal of this kind of tournament is to make every team play every weekend, ensuring
the continuity of the sporting activity. This is not a problem when n is even. However, if n
5
6 INDICE GENERAL
is odd, it is usual to leave a team aside every weekend which conspires with the mentioned
continuity.
We are interested in knowing about the existence of these kind of tournaments. And
for the n where they exist, we may try and answer the same question with some extra
conditions (as an example, no teams playing three consecutive weekends as a visitor).
Through integer linear programming, we showed the existance for n 13. This extends
previous results in the area, which showed existence for n 9. On the other hand, through
integer linear programming techniques, we studied extra conditions to these tournaments.
Finally, we proved that if we have a tournament for n teams and m is odd, then there
exists a tournament for n.m teams.
Captulo 1
Introduccion
1.1. Contexto
Esta tesis se enmarca dentro de una disciplina llamada sports scheduling que se encarga
de estudiar tecnicas para disenar campeonatos deportivos en forma eficiente. Disenar el
torneo implica decir que equipos juegan entre s cada fecha y quien sera el local. Dado un
formato de torneo particular, veremos mas adelante que a veces es sencillo armar el torneo
y otras veces no. Por ejemplo en el futbol argentino, hasta el 2014 haba 20 equipos y en
un torneo de 19 fechas jugaban todos contra todos. Preparar el fixture no es difcil. El
problema se vuelve mas complejo cuando ademas ponemos condiciones extra, por ejemplo:
los dos equipos de Rosario y Avellaneda no deben ser locales en la misma fecha. Otro
ejemplo es exigir que los equipos no sean visitantes tres veces seguidas. Entonces, saber si
existe un fixture es la primer pregunta que uno puede hacerse y por cada condicion extra,
aparece otra pregunta similar. As, las preguntas se pueden combinar con el objetivo de
lograr un torneo acorde con exigencias de la television, de la seguridad y tambien para
hacerlo mas equitativo.
Una vez que se sabe que existe un fixture, surgen a continuacion otras preguntas dentro
de Sports Scheduling. Cual es el mejor fixture de todos?. Como elegir el mejor? Se
pueden fijar varios objetivos que establecen distintos criterios. Un primer objetivo podra
ser minimizar la distancia viajada por los equipos. Por ejemplo, que un equipo de Buenos
Aires viaje de Jujuy a Chubut, despues a Misiones y finalmente a Santa Cruz pondra en
desventaja a este equipo. Probablemente, sea mejor aprovechar el viaje al norte para jugar
algun partido mas antes de volver.
Tambien se puede establecer un valor para cada viaje de una ciudad a otra, este valor
puede ser un promedio ponderado entre el tiempo o la distancia de viaje, el costo, etc.
El criterio mencionado concretamente da una funcion objetivo, esto es una funcion que
evalua cuan bueno es el fixture.
Si el objetivo es que los equipos no juegen de forma consecutiva de local o visitantes,
dado un fixture podemos contar la cantidad de veces que un equipo cambia su locala. En
este caso, se buscara el fixture cuya funcion objetivo de un valor maximo.
El problema es entonces elegir entre todos los fixtures, el de menor o mayor funcion
objetivo, dependiendo del problema. Este problema tiene dos grandes dificultades. La
primera es que muchas veces la funcion objetivo tiene muchos extremos locales, y por
7
8 CAPITULO 1. INTRODUCCION
lo tanto no hay un camino evidente a traves de las soluciones factibles que nos lleve al
extremo global. La otra dificultad es que el conjunto de soluciones factibles es muy grande,
a pesar de ser discreto y finito, su cardinal es muy grande.
Input: Un conjunto T = {t1 , t2 , . . . , tn } con los equipos, una matriz D Znn simetri-
ca donde dij representa la distancia de la ciudad del equipo i a la del equipo j y por ultimo
dos constantes l u.
Output: El torneo para los equipos de T donde se minimiza la distancia total recorrida
para los equipos y la cantidad maxima de partidos consecutivos como visitante esta entre
l y u.
No esta probado todava pero se asume que el problema es NP -hard. Si se pudo probar
en 2009 que sacando la restriccion de localas, si es un problema NP -hard, la prueba es de
Rishiraj Bhattacharyya en ??. Computacionalmente aparenta ser mucho mas difcil que el
Traveling Salesman Problem. Hay ejemplos de grupos de equipos con sus costos de viaje
y se ha intentado encontrar el mejor fixture segun cada cantidad de equipos. Se puede ver
en [6] que diez es la maxima cantidad de equipos en un torneo para el cual se conoce el
fixture optimo.
Dado que la cantidad de equipos es a veces pequena y que por diversas razones (por
ejemplo, economica) puede variar de ano a ano, se necesita saber como armar un fixture
para distintas cantidades de equipos. Consecuencia de ser tan pocos equipos, en la pri-
mera fase todos los equipos jugaran entre s cuatro veces, habra partidos los viernes y los
domingos.
1 2 1 6 1 5 1 4 1 3
6 3 5 2 4 6 3 5 2 4
5 4 4 3 3 2 2 6 6 5
Si la cantidad de equipos es par, hay un metodo sencillo para armar un fixture, basta
con seguir el esquema de el Cuadro 1.1. En ella pueden verse 5 pares de columnas. Cada
par de columnas representa una fecha del torneo. La primer fecha sera entonces as: El
equipo 1 recibe al equipo 2, el 6 recibe al 3 y el 5 recibe al 4. Se lee de la figura mirando
por filas, donde la primer columna tiene al local y la segunda al visitante. Estas seran
las primeras cinco fechas del torneo, que tiene diez, entonces, las ultimas cinco pueden ser
iguales que las primeras pero invirtiendo la locala. Cada vez que un equipo recibe a otro,
juegan entre s el viernes y el domingo.
Por que decamos que es sencillo armar este fixture? La razon es que la forma de
armarlo es simple, el ejemplo fue para seis equipos pero sera igual de facil para cualquier
cantidad par. Se puede ver en todos los pares de columnas, el 1 en el extremo superior
izquierdo. Luego, en la fecha 1 estan los equipos de 2 a 6 ordenados (recorriendo las
columnas en sentido horario) y en las fechas siguientes, se van girando, manteniendo ese
orden.
El formato del torneo propuesto para una cantidad n impar se llama Fixture con
sistema de Grand-Prix consiste en que los equipos seran separados en parejas (dejando de
lado una terna) y para cada par, alguno sera el local y jugaran entre s los dos partidos del
fin de semana. Por otra parte, la terna restante de equipos tendra uno que sera el local y
recibira a los otros dos equipos jugando contra uno el viernes y contra el otro el domingo.
Conseguimos as que todos los equipos jueguen dos partidos por fin de semana salvo solo
dos, que en vez de quedar libres, juegan un solo partido.
El partido donde un equipo recibe a otros dos sera llamado partido rally. El equipo
local en este partido rally sera llamado equipo rally local y a los dos equipos que lo visitan
los llamaremos equipos rally visitantes. La cantidad de fechas en este tipo de fixture es 2n.
Llamaremos EGP al problema de encontrar un fixture con estas caractersticas.
Al ser este un formato de torneo nuevo, no se sabe si existen fixtures que cumplan
estas condiciones. Por eso es de interes resolverlo. En el ano 2009, F. Bonomo, G. Duran y
J. Marenco estudiaron el problema EGP y muestran en [1] sus resultados. En el proximo
captulo mostraremos el modelo de programacion lineal entera que usaron para intentar
resolver el problema, lo llamaremos Modelo 1. Con ese modelado del problema encontraron
fixtures factibles para cinco, siete y nueve equipos. Mas adelante en ese captulo nosotros
propondremos un modelo nuevo para este mismo problema, al cual nos referiremos como
Modelo 2.
10 CAPITULO 1. INTRODUCCION
Ejemplo 1.1. En el Cuadro 1.2 mostramos un fixture factible para cinco equipos. Bajo el
ttulo de partido regular, se encuentra el partido no rally, ah hay dos sub columnas, una
corresponde a L que tiene al equipo local y otra V que tiene al visitante. Bajo el ttulo
partido rally tenemos tres sub columnas, la primera para el equipo rally local y las otras
dos para los equipos rally visitantes. Cada fila representa una fecha distinta.
Se puede obervar en el Cuadro 1.3 que el equipo 5 es rally visitante desde la sexta
fecha hasta la novena. Esto quiere decir que en 4 semanas juega solo 4 partidos, mientras
que el el equipo 4 no es visitante mas de 2 veces seguidas.
Fechas
Equipo
1 2 3 4 5 6 7 8 9 10
1 Vr V L L V r Vr L V Vr L
2 L Vr Vr L V L L Vr V Vr
3 Vr Vr L Vr Vr L V L L V
4 V L Vr Vr L V Vr L L Vr
5 L L V V L Vr Vr Vr Vr L
Cuadro 1.3: Esquema de localas para el fixture del Cuadro 1.2. Los equipos que tiene
una r como subndice a lado de la V de visitante significa que en esa fecha son equipos
rally visitantes.
todos los equipos sean igual cantidad de veces equipo rally local?
Todas estas condiciones hacen que el fixture sea mas equitativo, por eso tiene interes
responderlas e intentaremos hacerlo modelandolas en el Captulo 2. Veamos ahora otro
ejemplo que respeta algunas condiciones extra, y es por lo tanto, mas justo.
Ejemplo 1.2. En el Cuadro 1.4, vemos un fixture para siete equipos con condiciones
extra, aqu ningun equipo juega mas de tres fechas seguidas como local o visitante.
Cuadro 1.4: Fixture factible para siete equipos con condiciones extra.
En el Cuadro 1.5, mostramos a lo largo del torneo, las localas de cada equipo. Ah se
puede ver como para ningun equipo hay tres V o L seguidas. Lo que s se puede ver es
que los unicos equipos que les toca ser rally visitantes en fines de semana consecutivos son
el 3 y el 5. Esto sera tal vez una desventaja para ellos y hace que el fixture tampoco sea
totalmente equitativo.
12 CAPITULO 1. INTRODUCCION
Fechas
Equipo
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 V L Vr L Vr L Vr V L V L Vr V L
2 Vr L Vr L L V V L V Vr L V L Vr
3 L Vr L V V L V r Vr L V L Vr V L
4 L Vr L Vr V L V L L Vr V L Vr V
5 L V V L Vr V L Vr Vr L V L L Vr
6 Vr L V V L Vr L V V L Vr L Vr L
7 V V L Vr L Vr L L Vr L Vr V L V
Cuadro 1.5: Esquema de localas para el fixture del Cuadro 1.4. Los equipos que tiene
una r como subndice a lado de la V de visitante significa que en esa fecha son equipos
rally visitantes.
Una vez resuelto el problema de la existencia de los fixtures para cierta cantidad de
equipos, surge la segunda pregunta mencionada al final del captulo anterior. Supongamos
que tenemos como dato los costos del transporte para el viaje para ir de una ciudad a otra,
tambien se podra saber el tiempo de viaje, la distancia recorrida u otras magnitudes. Todas
estas cantidades pueden ser englobadas en una nueva que llamaremos costo. Entonces
tendramos que el costo de ir de una ciudad a otra sera representado por un numero
positivo. Con toda esta informacion disponible, se podra calcular cuanto debe costarle a
cada equipo participar del torneo. Para calcularlo, se toma el fixture y se arma el recorrido
que tiene que hacer cada equipo, desde que empieza el torneo en su ciudad, hasta que
termina el torneo y tiene que volver. Cada tramo del viaje entre fecha y fecha tiene el
costo calculado, y eso se va sumando hasta conseguir la cifra total para el torneo.
Sabiendo eso, podemos intentar contestar la siguiente pregunta: Cual es el fixture que
hace que todos los equipos tengan el menor costo posible a lo largo del torneo?
Este problema es mucho mas difcil que el EGP, tiene el nombre de Fixture con sis-
tema de Grand-Prix de distancia mnima (MGP). Haciendo un pequeno paralelo con lo
mencionado sobre TTP en el comienzo del captulo: sabemos que si n es par no es difcil
conseguir fixtures factibles ya que el metodo que dimos nos da muchos. En cambio, s es
difcil conseguir el que minimice las distancias de viaje. En el problema MGP tenemos que
resolver una minimizacion similar pero partiendo de una base distinta, ya no es sencillo
conseguir los fixtures factibles.
Esta ultima version del problema sera abordada en el Captulo 3. En el mostraremos
como modelarlo y la falta de resultados con los solvers de programacion lineal entera.
Entonces presentaremos una solucion alternativa que sera tomar una solucion factible del
modelo y mejorarla mediante una heurstica.
1.4. RESUMEN DE LA TESIS 13
2.1. Modelo 1
Existe un modelo para la primera version del problema, este fue propuesto en [1]. Si es
n la cantidad de equipos (sera un numero natural), se define P = {1, 2, . . . , n} el conjunto
de equipos y F = {1, 2, . . . , 2n} el conjunto de fechas del torneo.
En este modelo, hay que definir tres juegos de variables que son los siguientes: Para
cada i, j P distintos y para cada f F se define la variable binaria xijf tal que xijf = 1
si y solo si el equipo i recibe al menos en un partido al equipo j durante la fecha f .
Tambien para cada i, j P distintos y para cada f F se define la variable binaria wijf
de modo que wijf = 1 si y solo si el equipo i recibe a j en la fecha f y juegan dos partidos,
es decir, no juegan en un partido rally. Finalmente, para cada i P y f F se define la
variable binaria yif tal que yif = 1 si y solo si el equipo i es el rally local en la fecha f .
Con todas estas variables, la siguiente formulacion de programacion lineal entera mo-
dela el problema de encontrar un fixture para n equipos (donde n es impar).
X
(xijf + wijf ) = 2 i, j P (i 6= j) (2.1)
f F
X
(xijf + xjif ) = 1 + yif i P, f F (2.2)
j6=i
X
yif = 1 f F (2.3)
iP
wijf xijf i, j P (i 6= j), f F (2.4)
wijf 1 yif i, j P (i 6= j), f F (2.5)
xjif 1 yif i, j P (i 6= j), f F (2.6)
xijf , wijf {0, 1} i, j P (i 6= j), f F (2.7)
yif {0, 1} i P, f F (2.8)
La ecuacion (2.1) asegura que cada equipo juega de local dos veces contra cada uno de
15
16 CAPITULO 2. MODELOS DE PROGRAMACION LINEAL ENTERA PARA EGP
los otros equipos, la ecuacion (2.2) dice que cada equipo juega contra solo un equipo en
cada fin de semana a menos que sea el equipo rally local. La ecuacion (2.3) garantiza que
exactamente un equipo es rally local en cada fecha. Finalmente, el resto de las condiciones
fuerza a la correcta relacion entre las variables: (2.4) asegura que un partido es jugado dos
veces solo si es jugado al menos una vez, (2.5) dice que el equipo rally local no juega dos
partidos contra el mismo equipo en un fin de semana y la ecuacion (2.6) garantiza que el
equipo rally local es efectivamente local.
Es importante destacar que el modelo con las ecuaciones (2.1)-(2.8) no necesita funcion
objetivo, y al ser un problema de factibilidad, no es facil de resolver con los algoritmos dis-
ponibles basados en branch-and-bound, por lo tanto, modificaremos el modelo. Los autores
proponen modificar el modelo por uno de optimizacion, es decir, con funcion objetivo.
La formulacion alternativa se reemplaza la ecuacion (2.1) por
X
(xijf + wijf ) 2 i, j P (i 6= j) (2.9)
f F
X
(xijf + xjif ) 1 + yif i P, f F (2.10)
j6=i
X
(xijf + xjif ) 2yif i P, f F (2.11)
j6=i
En esta formulacion alternativa, cada equipo puede jugar hasta dos partidos por fin de
semana, exceptuando el equipo rally local que jugara siempre exactamente dos partidos.
Notar que la condicion (2.11) es necesaria para evitar fixtures no deseados. Por ejemplo,
un fixture que deja libre a un equipo por fecha sera factible en el modelo (2.3)-(2.10).
La funcion objetivo suma todos los partidos no-rally que hay en el torneo. Sabemos
que hay (n3)
2 por fecha y que hay 2n fechas. Por lo tanto en el caso de obtener un fixture
factible, el valor de la funcion objetivo debe ser: n(n 3).
Por otra parte, si la funcion objetivo toma el valor n(n 3), la solucion factible donde
se alcanza ese maximo debe ser un fixture valido. Las variables yif obligan a los partidos
no-rally a estar correctamente distribuidos en las fechas.
2.2. Modelo 2
Proponemos ahora un nuevo modelo para EGP, al igual que en el modelo anterior,
se define P = {1, 2, . . . , n} el conjunto de equipos y F = {1, 2, . . . , 2n} el conjunto de
fechas del torneo. El conjunto de variables binarias x esta indexado sobre i, j, k, f donde
i, j, k P y f F .
2.2. MODELO 2 17
X X n3
xijjf = f F (2.12)
2
iP jP
X X X
xijkf = 1 f F (2.13)
iP jP kP/j<k
X X X
xijjf + xijkf +
f F f F kP/j<k
X X
+ xikjf = 2 i, j P/i 6= j (2.14)
f F kP/k<j
X X
(xijkf + xkijf + xjkif ) = 1 i P f F (2.15)
jP kP/j6=i
xijkf {0, 1} i, j, k P f F (2.16)
Nuevamente modelamos EGP como problema de factibilidad. Como dijimos antes, este
no es adecuado para tratar con los algoritmos basados en branch-and-bound. Por lo tanto,
lo modificamos para conseguir una formulacion alternativa.
Para la formulacion alternativa reemplazamos la ecuacion (2.12) por la siguiente:
X n3
f F : xijjf (2.17)
2
i,jP
Con la relajacion de la igualdad (2.12) en una desigualdad, alguna de las variables xijjf
podran ser ceros haciendo a la solucion no factible. Para ello se elije tal funcion objetivo,
para forzar a las variables a tomar el valor uno hasta que la suma 2.17 valga n3 2 en todas
las fechas del torneo.
Para contestar alguna de las preguntas extra, presentadas en la Seccion 1.2, se pueden
agregar algunas restricciones mas, en este trabajo nos dedicamos a las mismas que en [1]
para poder comparar los resultados de ambos modelos. Algunas de ellas no las estudiamos
porque para pequenas cantidades de equipos, no son factibles.
Presentamos las distintas condiciones extra con sus respectivas restricciones para el
modelo:
5. Ningun equipo juega de visitante 4 fechas seguidas (tambien igual a las 2 anteriores
poniendo el 4 donde corresponde y agregando los terminos correspondientes).
2.3. COMPARACION DE LOS MODELOS 19
6. Ningun equipo juega de local o visitante 3 fechas seguidas. Uso la condicion (2.19) y
agrego la siguiente ecuacion que limita la cantidad de partidos de local consecutivos:
X X
(xi,j,k,f + xi,j,k,f +1 + xi,j,k,f +2 ) 2 i P f F
jP kP/jk
7. Ningun equipo juega de local o visitante 4 fechas seguidas (igual al caso anterior,
cambiando los 3 por 4).
Esta formulacion debera verificar lo siguiente: Si el optimo del modelo alternativo es
una solucion factible con valor n(n 3) esa solucion lo es tambien del modelo original
de factibilidad.
Si una solucion tiene valor n(n3), entonces vale la igualdad en las inecuaciones (2.17)
pues si para algun f0 :
X n3 XX X
xijjf < xijjf < n(n 3)
2
i,jP iP jP f F
Tipo de Cantidad de
restricciones restricciones
2.1 n(n 1)
2.3 2n
2.4 2(n 1)n2
2.5 2(n 1)n2
2.6 2(n 1)n2
2.9 n(n 1)
2.10 2n2
2.11 2n2
Totales O(n3 )
Cuadro 2.1: Cantidad de restricciones para cada tipo en el Modelo 1 segun la cantidad
de equipos.
Tipo de Cantidad de
restricciones restricciones
2.13 2n
2.14 n(n 1)
2.15 2n2
2.17 2n
Totales O(n2 )
Por ultimo, las Figuras 1 y 2 muestran un grafico que compara la cantidad de variables
y restricciones en funcion de la cantidad de equipos. Se puede ver en ellos que para los
valores de n que trataremos en la siguiente seccion, las diferencias estan marcadas pero
no hace que sean cantidades inmanejables por los solvers actuales.
El Modelo 2 tiene una ventaja, o al menos pareciera tenerla ya que si quisieramos decir
en la fecha 1, el equipo 1 es rally local y recibe al 2 y al 3 en el modelo nuevo basta con
poner x1231 = 1 mientras que en el modelo anterior necesitamos y11 = 1 para decir que el
equipo 1 es rally local, x121 = x131 = 1 para decir que el equipo 1 juega de local contra
los equipos 2 y 3 en la fecha 1 y por ultimo, w121 = w131 = 0 para decir que el equipo 1
es local contra los equipos 2 y 3 pero no juegan 2 partidos en esa fecha.
Variable Cantidad
xijf 2n3
Modelo 1 wijf 2n3
yif 2n2
Modelo 2 xijkf n3 (n 1)
Cuadro 2.4: Resultados computacionales del Modelo 1 con desigualdades validas adicio-
nales (sin ellas solo la instancia ? termino en menos de una hora). Donde hay un signo de
interrogacion, el algoritmo no termino en una hora.
Por otra parte, los resultados del modelo propuesto en este trabajo resultaron un poco
mejores en la practica. Esto no era tan claro a priori ya que no sale claramente beneficiado
en la comparacion de la cantidad de restricciones y la cantidad de variables vista en la
seccion anterior.
En el Cuadro 2.5 se presentan los resultados del Modelo 2. En el se puede ver como
el Modelo 2 logro responder muchas preguntas que el Modelo 1 no haba podido. Por
ejemplo, sobre la factibilidad de fixtures para once equipos. Tambien pudo contestar las
preguntas de si exista fixture con las distintas condiciones extra para 7, 9 y 11 equipos.
Por ultimo, con el Modelo 2 se pudo encontrar un fixture factible para 13 equipos. En
esta instancia, no se pudo saber si exista con condiciones extra, ah el solver no llego a
terminar de resolver ni siquiera en 8 horas.
22 CAPITULO 2. MODELOS DE PROGRAMACION LINEAL ENTERA PARA EGP
Cuadro 2.5: Resultados computacionales del Modelo 2. Donde las filas que ponen con-
diciones de locala para 4 fechas consecutivas son factibles como consecuencia de que las
filas de 3 tambien lo son.
2.3. COMPARACION DE LOS MODELOS 23
En este captulo trataremos el problema MGP. Los datos iniciales seran: una cantidad
n de equipos y una matriz C de n n que contiene todos numeros reales no negativos.
Esa matriz representara los costos de ir de una ciudad a otra. Por ejemplo, el valor cij
representara el costo de ir de la ciudad donde esta el equipo i hasta la ciudad donde esta el
equipo j, tambien podra representar el tiempo de viaje o un promedio ponderado entre
ellos. Dada esta interpretacion, es claro que en su diagonal, la matriz tendra todos ceros.
Sera razonable ademas pedir que la matriz sea simetrica, en nuestro caso no lo pediremos
porque no es estrictamente necesario.
La matriz con la que nosotros trabajaremos, sera tomada de la liga de voley femenino
argentino real, y representara simplemente los kilometros de distancia entre una ciudad y
otra, por eso, en nuestro ejemplo sera una matriz simetrica.
3.1. Modelo 3
El primer paso para tratar esta nueva version del problema es adaptar el Modelo 2 de
programacion lineal entera que tenamos en EGP al problema MGP.
Trabajando en EGP en el Captulo 2 se tuvo que agregar una funcion objetivo ficticia
para obtener rendimiento optimo de los solvers de programacion lineal entera. Ahora,
en esta nueva version del problema, tenemos una funcion objetivo natural que sera una
funcion que sume los costos de todos los equipos.
Quisieramos que la funcion objetivo cuente los recorridos de cada equipo. Teniendo una
matriz simetrica C tal que cij representa la distancia de la ciudad donde esta el equipo i
hasta la ciudad del equipo j. Para conseguir esto, creamos un nuevo juego de variables,
dado i, j, k P distintos y dado f F0 = F {0} = {0, 1, . . . , 2n 1, 2n}, la variable
zijkf sera binaria y valdra uno solo si el equipo i juega en la fecha f en el estadio de j
y en la fecha f + 1 en el estadio de k. La variable con f = 0 representa para un equipo
el viaje desde su ciudad hasta la ciudad donde juega el primer partido. Analogamente, la
variable con f = 2n cuenta el viaje desde la ciudad donde se juega el partido de la ultima
fecha hasta su ciudad.
Es importante notar que, a diferencia de las variables xijkf , ahora el i, j y k pueden
ser iguales o no, no hay restricciones para ellos.
25
26 CAPITULO 3. UNA HEURISTICA PARA MGP
XXX X
mn cjk zijkf (3.1)
iP jP kP f F0
Lo ultimo por adaptar del Modelo 2 visto antes sera agregar las restricciones que ligan
entre s a los dos grupos de variables del modelo. Estas apareceran despues de las restric-
ciones del Modelo 2. Por lo tanto, las restricciones del modelo nuevo, al cual en adelante
llamaremos Modelo 3 seran:
X X
(xjiuf + xk,i,u,f +1 ) + (xjuif + xk,u,i,f +1 ) zijkf (3.2)
uP/iu uP/i<u
i, j, k P / i 6= j, i 6= k, f F / f < 2n
XX X
xikuf + xj,i,u,f +1 + (3.3)
kP uP uP/iu
X
+ xj,u,i,f +1 ziijf + 1 i, j P / i 6= j, f F / f < 2n
uP/i<u
X X
xj,i,u,f + xj,u,i,f + (3.4)
uP/iu uP/u<i
X X
+ xi,k,u,f +1 zijif + 1 i, j P / i 6= j, f F / f < 2n
kP uP/ku
XX
zijkf = 1 i P, f F (3.5)
jP kP
X X
xjik1 + xjki1 ziij0 i, j P (3.6)
kP/ik kP/k<i
X X
xj,i,k,2n + xj,k,i,2n zi,j,i,2n i, j P (3.7)
kP/ik kP/k<i
Como lo habamos supuesto, el problema MGP es mucho mas difcil que el EGP.
Buscar un fixture para un torneo de cinco o siete equipos era relativamente rapido, las
instancias donde testeamos el modelo en SCIP, no se puede conseguir buenos resultados.
A veces es posible encontrar algunas soluciones factibles, pero no podemos saber cuan
buenas son ya que la cota superior dada por la relajacion lineal es muy mala. Otras veces,
para las instancias mas grandes, no consigue siquiera una solucion factible. Para testear el
modelo de programacion lineal entera y la heurstica, creamos veinte instancias de prueba.
Tomando como datos las distancias entre doce equipos argentinos de voley, armamos las
primeras cinco instancias tomando cinco equipos al azar entre los doce. Luego, armamos
las segundas cinco instancias de la misma forma pero ahora eligiendo siete equipos. Las
instancias once a quince son de nueve equipos y por ultimo, de la dieciseis a la veinte son
de once equipos.
En el Cuadro 3.1 mostramos el tiempo en que tarda en conseguir la primer solucion
factible y la cantidad de soluciones factibles al momento de cortar la corrida. Las instancias
para cinco equipos corrieron durante treinta minutos, las de siete equipos noventa minutos,
las de nueve equipos por ciento ochenta y por ultimo, las de once equipos por seis horas.
Como se puede ver en el Cuadro 3.1, SCIP nunca llega a encontrar el optimo, o al
menos, nunca llega a saber si la solucion factible encontrada es el optimo. Las instancias
16 a 20 no estan en la tabla, ya que al cabo de seis horas, no encontro solucion factible.
Tampoco encontro una solucion en la instancia 12.
28 CAPITULO 3. UNA HEURISTICA PARA MGP
2. Calcular N(s)
5. Output: s
2. Inicializar: i = 0 y s0 = s
3. s = BLe (s)
4. s = BLf (s)
5. Si Obj(s) Obj(s ): s = s
6. s = Perturbacion Aleatoria ( s )
7. i = i + 1
8. Si i C, ir a 3.
9. Output: s.
se hace de esta forma porque la solucion no puede ser peor que la anterior. La busqueda
local devuelve el input si el en el vecindario no hay una solucion mejor.
En el paso 5 se almacena la solucion factible de menor costo hasta el momento. En el
paso 6, se mezcla aleatoriamente el fixture para que la solucion s salga del extremo local
donde puede estar encerrada.
Cuadro 3.2: Resultados conseguidos por la heurstica usando como fixture inicial el dado
por el Modelo 2. Los tiempos estan expresados en segundos.
32 CAPITULO 3. UNA HEURISTICA PARA MGP
Cuadro 3.3: Resultados conseguidos por la heurstica usando como fixture inicial el dado
por el Modelo 3. Los tiempos estan expresados en segundos.
Captulo 4
Multiplicacion de fixtures
Una vez conseguidos todos los fixtures que el modelo de programacion lineal entera
nos pudo dar, buscamos la forma de usarlos para armar fixtures para valores de n mas
grandes.
En este captulo se demostrara una serie de hechos que nos permitira probar, al final,
que dado un fixture para n equipos, con n impar, podremos conseguir un fixture para n.m
equipos siendo m cualquier numero impar. A medida que avanzamos con las propiedades
que nos daran el resultado esperado, en paralelo iremos mostrando un ejemplo para armar
un fixture para 15 equipos partiendo de uno de 5 mostrado en el Cuadro 4.1 mas adelante.
Lema 4.1. Sea n impar, dado que 2n es la cantidad de fechas de un torneo entonces cada
equipo es rally-visitante exactamente cuatro veces.
Los grafos que permiten mas de un arista entre sus vertices se llaman multigrafos, el
multigrafo que mencionaremos a continuacion es un caso particular de multigrafo, ya que
podra tener hasta dos aristas entre cada par de vertices.
Dado un equipo A, llamamos E1 , E2 , . . . , Em a los equipos que recibe en fines de
semana rally. Sean V = {E1 , E2 , . . . , Em } y E ={(i, j) / i y j visitan a A en el mismo fin
de semana}.
Entonces GA = (V, E) es un multigrafo no dirigido. En los siguientes lemas estudiare-
mos este grafo.
33
34 CAPITULO 4. MULTIPLICACION DE FIXTURES
solo partido, tendra que visitarlo y jugar otro partido, es decir, lo visito como equipo rally
visitante dos veces.
Al ser par la cantidad de aristas que salen de cada vertice, el multigrafo se llama
Euleriano y por lo tanto, se puede separar en ciclos.
Lema 4.3. Dado un equipo A, este visita como equipo rally a exactamente dos equipos.
Lema 4.4. Dado un equipo A y un equipo B al que A visita en un fin de semana rally.
Entonces A aparece en exactamente dos ciclos de grafos GB correspondientes a sus visitas
como equipo rally visitante a dos equipos distintos.
Definicion 4.5. Dada una arista de un grafo, tenemos sus dos vertices. Arbitrariamente
vamos a elegir uno de ellos y decir que esta marcado mientras que el otro vertice no.
Observacion 4.6. Sea C un ciclo del grafo GA formado por los visitantes de cierto equipo
A. Marcando un vertice en cada arista, es posible elegir una vez a cada equipo. La forma
de hacerlo es recorriendo el ciclo y eligiendo alternadamente los vertices.
Figura 1: Grafos que resultan de unir a los equipos que visitan juntos como rally-visitantes
a un cierto equipo. Cada ciclo tiene en el centro al equipo local. El asterisco indica por
que equipo se empieza a recorrer el ciclo.
1 5 2 3 4
5 2 4 1 3
2 4 3 5 1
3 1 5 4 2
4 3 1 2 5
nm equipos, por eso, debemos mostrar la existencia de ellas para cualquier m natural
e impar. Si tomamos un grupo abeliano (G, ) de orden m y armamos la tabla de la
operacion , conseguimos una matriz simetrica. Si por ejemplo armamos la tabla para el
grupo (Zm , .) obtenemos una mariz cuya diagonal tiene los m valores distintos. No verifica
que la posicion (k, k) tenga el numero k pero para conseguirlo, basta con permutar los
numeros adecuadamente.
La matriz que se usara en el ejemplo para n = 5 y m = 3 es una matriz de 3 3 que
se puede ver en la Figura 3.
1 3 2
3 2 1
2 1 3
Ademas, hay un uno en la posicion (2,3), eso quiere decir que en el segundo fixture
de los tres que juntamos, ponemos como locales a equipos del grupo 2 (azul en la figura)
y como visitantes a los del grupo 3 (verde en la figura). Analogamente, como el cuadro
latino lo elegimos simetrico, hay un 1 en la posicion (3,2), entonces completamos el tercero
y ultimo de los fixtures poniendo como locales a los equipos del grupo 3 (verdes) y a los
del grupo 2 (azules) como visitantes.
Cuadro 4.2: Primer paso: juntamos los tres fixutres de tamano n = 5 y asignamos los
grupos de equipos. Este no es todava un fixture factible.
de distintos grupos, es decir, el unico partido rally de la fecha sera el que corresponde al
numero de la diagonal en la matriz, supongamos para fijar ideas que es el 1.
Como desarmar esos partidos rally? Supongamos para simplificar la notacion, que el
equipo A recibe a B y C en un partido rally del fixture conocido de n n. Despues de
analizar los ciclos del grafo GA y haber elegido a una vez a cada equipo, se procede a
mirar cual de los dos equipos (B o C) es el elegido en ese fin de semana que se busca
desarmar. Si es B, entonces se saca a B de ese partido y se deja al equipo A recibiendo
a C solo, ah disputaran dos partidos. Cuando se haga esto para todos los partidos rally
correspondientes a esa fecha, se tendra todos los equipos B, salvo uno, ese equipo B faltante
es el del primer grupo de equipos. Entonces se tiene a todos los equipos B salvo el 1.
Si en la fecha jugaban los equipos del grupo i contra los del j, entonces el equipo B del
grupo i jugara contra el equipo B del grupo j. Como cada equipo es elegido dos veces en
cada grupo de fechas, entonces habra otro momento en donde separaremos a los equipos
de B salvo el del grupo 1, ah podremos hacer que jueguen de nuevo entre s invirtiendo
la locala.
Hemos sacado a B del partido rally donde A recibe a B y C, cuando recibe entonces
A a B en el torneo? Afirmamos antes que de las dos veces que B recibe a A en el torneo
de n equipos en una es elegido (y por lo tanto sacado) y en la otra no. Por lo tanto, en la
otra vez que visita a A como equipo rally, el otro equipo rally visitante debe ser elegido y
por lo tanto sacado y en esa fecha jugaran los dos partidos que corresponde a A recibir al
equipo B.
As se logra armar con los m1 equipos separados de cada fecha, m1 2 partidos nuevos.
Por lo tanto, tenemos m( 2 + 1) + 2 partidos por fecha, esto es exactamente mn3
n3 m1
2 +1
que es el numero necesario.
Ademas, la cantidad de fechas, poniendo m grupos de 2n fechas es 2mn. Tambien el
numero esperado.
Siguiendo los ciclos, en el Cuadro 4.3 podemos ver como quedan desarmados los par-
tidos rally. Por ejemplo, para la primer fecha, tenemos que el equipo 1 azul recibe al 4 y 5
verde y el equipo 1 verde recibe al 4 y 5 azul. El grafo que corresponde a los equipos que
visitan a 1 esta orientado de forma que esta el arista (4,5) pero no el arista (5,4). Entonces
el equipo elegido sera el equipo 4. Sacamos los equipos 4 de los partidos rally para que
jueguen entre s y los equipos numero 1 recibiran a los equipos 5 (del color contrario).
Hay un caso particular, que se trata un poco distinto. Como el grafo de los equipos que
visitan a 4 se divide en dos ciclos disjuntos que tienen solo dos equipos, entonces, aparece
en el grafo el arco (1,2) y el (2,1). La pregunta es entonces: Cual miramos primero?. Para
contestar esta pregunta esta el asterisco en el grafo. El equipo 1 tiene un asterisco, eso
quiere decir que sera elegido primero. Por eso, en las fechas donde el equipo 4 es rally
local contra los equipos 1 y 2, el primero en ser elegido es el 1. En la fecha 7 los equipos
1 jugaran entre s mientras que en la fecha 9 seran los equipos 4.
Una vez hecho esto, podemos reemplazar estos cambios en lo que tenamos hasta ahora
y tener terminado el primer grupo de fechas. Eso se puede ver en el Cuadro 4.4.
Repitiendo este proceso para el segundo y tercer grupo de fechas, podemos obtener el
fixture completo para 15 equipos, este tendra 30 fechas. Presentamos la solucion final para
hacer algunas observaciones. El fixture terminado se puede ver en el Cuadro 4.5
4.1. COMBINACION DE M FIXTURES PARA N EQUIPOS. 39
Cuadro 4.3: Como transformar dos partidos rally en tres partidos regulares.
estamos mirando con quien juegan los equipos del grupo k en el k-esimo grupo de
fechas, los partidos rally no fueron desarmados. Ademas, por ser ese grupo de fechas
un torneo de n n valido, cada equipo recibe dos veces a cada uno de los otros.
3. Tambien para simplificar la notacion, supongamos que hablamos del equipo A del
grupo i y del equipo B del grupo j. Como antes, supongamos que en la posicion (i, j)
y (j, i) estara el numero k. Entonces en el k-esimo grupo de fechas jugaran entre s los
equipos del grupo i y los del j. Si en el fixture de n n con el que comenzamos hay
una fecha donde el equipo A recibe al equipo B sin estar en un partido rally, entonces,
gracias al numero k en la posicion (i, j) el equipo A del grupo i recibira al equipo
B del grupo j. Como el fixture es valido, tambien el equipo B recibe al A en alguna
otra fecha, entonces el equipo B del grupo j tambien recibe al equipo A del grupo
i. Si A recibiera a B en un partido rally, entonces, habra exactamente dos fechas
donde A recibe a B en partidos rally. En una de ellas, B sera elegido y no jugara con
A, sino con otro equipo B de otro grupo. Pero en el fin de semana donde B no es
elegido, estos jugaran entre s dos partidos con A como local.
Quedara para trabajo futuro conocer las condiciones suficientes mas debiles para que este
tipo de propiedades se conserven para cantidades de equipos mas grandes.
5 7 9 11 13 15 17 19
21 23 25 27 29 31 33 35 37 39
41 43 45 47 49 51 53 55 57 59
61 63 65 67 69 71 73 75 77 79
81 83 85 87 89 91 93 95 97 99
Figura 4: El Teorema 4.7 combinado con los resultados computacionales obtiene solucio-
nes factibles para los numeros marcados en azul.
Observacion 4.9. Dado un numero n impar cualquiera, basta con conseguir un fixture
de tamano p, donde p es algun numero primo que divide a n y con eso podemos armar el
fixture para n equipos.
42 CAPITULO 4. MULTIPLICACION DE FIXTURES
En los primeros captulos de este trabajo propusimos un nuevo modelo para EGP. Los
resultados fueron muy buenos, conseguimos fixtures factibles para instancias de mayor
tamano que las que se conocan hasta el momento. Ademas, el modelo nuevo tiene unas
variables que permiten expresar las restricciones que vienen del torneo de forma sencilla
en las ecuaciones. Queda para trabajo futuro pensar como hacer para conseguir fixtures
factibles para una cantidad mayor de equipos. Las opciones son por lo menos tres, se
podra buscar una nueva forma de modelar el problema o tambien se podra intentar
encontrar familias de desigualdades validas. Tambien, se podra disenar una heurstica
para encontrar soluciones factibles.
Una vez que comenzamos a tratar con MGP, la tarea fue mucho mas difcil, ya no era
posible conseguir la solucion optima con el solver de programacion lineal entera. Enton-
ces, tomamos un camino alternativo. Si el solver no consiguio siquiera soluciones factibles,
la heurstica permitio conseguir un fixture bueno. En cambio, si el solver pudo conseguir
alguna solucion factible, con la heurstica la hemos podido mejorar en un poco y conseguir
una solucion relativamente buena. Queda para trabajo futuro conseguir por un lado algun
buen algoritmo heurstico que pueda mejorar mucho una solucion factible cualquiera, in-
cluso las conseguidas por el modelo que no contempla minimizar distancias. Por otro lado,
se puede intentar demostrar que la solucion factible es efectivamente buena y que no se
puede mejorar significativamente.
En el Captulo 4 conseguimos un resultado que nos da una condicion suficiente para la
existencia de fixtures. Sirve por ejemplo para saber para que cantidades de equipos tenemos
que enfocarnos en conseguir fixtures factibles segun lo dicho mas arriba. No necesitamos
por ejemplo encontrar un modelo que nos de una solucion factible para 21 equipos, pues
este lo conseguimos usando el Teorema 4.7. Lo que queda por contestar en el futuro es:
Dado un numero p primo, existe un fixture para p equipos?. No parece una pregunta
para nada sencilla. Lo que logramos en este trabajo son soluciones factibles para algunos
valores pequenos y una forma de multiplicarlos. No conocemos argumentos teoricos que
nos aseguren la existencia de soluciones factibles. Sera un proyecto ambicioso intentar
encontrar ese argumento mencionado.
43
44 CAPITULO 5. CONCLUSIONES Y TRABAJO FUTURO
Bibliografa
[1] F. Bonomo, G. Duran, y J. Marenco, Exploring the existence of fixtures for scheduling
sport leagues with odd numbers of teams and grand-prix weekends. VI ALIO/EURO
Workshop on Applied Combinatorial Optimization (2008).
[4] Martin, Olivier C., and Steve W. Otto. Combining simulated annealing with local
search heuristics..Annals of Operations Research 63.1 (1996): 57-75.
[5] K. Easton, G. Nemhauser, y M.A. Trick, The Traveling Tournament Problem des-
cription and benchmarks. T. Walsh editor, Principles and Practice of Constraint Pro-
gramming, Vol 2239 of Lecture Notes in Computer Science, 580-584. Springer, 2001.
[6] http://mat.gsia.cmu.edu/TOURN/
45