Este programa resuelve el problema de la organización de torneos en formato Single Round Robin (SRR) utilizando tres formulaciones diferentes: tradicional, basada en permutaciones y basada en emparejamientos (matching).
Los torneos en formato round robin, también conocidos como "todos contra todos", son ampliamente utilizados en diversas competiciones deportivas y en situaciones que requieren una organización similar. Este proyecto presenta tres enfoques diferentes basados en programación lineal entera para resolver el problema de programación de estos torneos.
-
Formulación Tradicional: Esta formulación es intuitiva y eficiente en términos de cantidad de variables, proporcionando un modelo más fácil de entender y trabajar.
-
Formulación Basada en Permutaciones: Aunque presenta problemas de escalabilidad debido a la alta cantidad de variables y restricciones a medida que aumenta el número de equipos, ofrece una estructura flexible para modelar variantes de torneos round robin.
-
Formulación Basada en Emparejamientos (Matching): Proporciona un mayor valor funcional en la relajación lineal asociada, lo que puede ser beneficioso cuando la dimensión del problema impide el uso de métodos como branch-and-cut.
Para ejecutar el script que resuelve el problema SRR (Single Round Robin), se utilizan varios parámetros que se describen a continuación. El script se ejecuta utilizando argparse para manejar estos parámetros.
--variant: Define la variante del problema a resolver. Puede tomar los valorestraditional,matching, opermutation. Por defecto, estraditional.--entera: Indica si las variables deben ser binarias (enteras) en lugar de continuas. Toma un valor booleano (TrueoFalse). Por defecto, esTrue.--file: Especifica el archivo de configuración que contiene los datos del problema. Este parámetro es requerido.--seed: Establece la semilla para la generación de números aleatorios, lo cual es útil para reproducibilidad. Por defecto, es42.
Para resolver el problema de programación de torneos en formato Single Round Robin (SRR), se requiere un archivo de configuración que contenga la información necesaria sobre los equipos y los costos asociados a cada partido en cada ronda. A continuación, se detalla el formato que debe tener este archivo de entrada.
El archivo de configuración debe estar estructurado de la siguiente manera:
- Primera línea: Indica la cantidad de equipos.
- Líneas siguientes: Cada línea contiene una tupla
(i, j), r, cque especifica el costocde que el equipoijuegue contra el equipojen la rondar.
archivo 4_teams.srr
- Primera línea:
4(Número de equipos). - Líneas siguientes:
(0, 1), 0, 3: Si el equipo0juega contra el equipo1en la ronda0con un costo de3.(0, 2), 0, 8: Si el equipo0juega contra el equipo2en la ronda0con un costo de8.(0, 3), 0, 1: Si el equipo0juega contra el equipo3en la ronda0con un costo de1.(0, 1), 1, 4: Si el equipo0juega contra el equipo1en la ronda1con un costo de4.(0, 2), 1, 6: Si el equipo0juega contra el equipo2en la ronda1con un costo de6.(0, 3), 1, 9: Si el equipo0juega contra el equipo3en la ronda1con un costo de9.(0, 1), 2, 2: Si el equipo0juega contra el equipo1en la ronda2con un costo de2.(0, 2), 2, 4: Si el equipo0juega contra el equipo2en la ronda2con un costo de4.(0, 3), 2, 7: Si el equipo0juega contra el equipo3en la ronda2con un costo de7.(1, 2), 0, 5: Si el equipo1juega contra el equipo2en la ronda0con un costo de5.(1, 3), 0, 1: Si el equipo1juega contra el equipo3en la ronda0con un costo de1.(1, 2), 1, 3: Si el equipo1juega contra el equipo2en la ronda1con un costo de3.(1, 3), 1, 9: Si el equipo1juega contra el equipo3en la ronda1con un costo de9.(1, 2), 2, 4: Si el equipo1juega contra el equipo2en la ronda2con un costo de4.(1, 3), 2, 8: Si el equipo1juega contra el equipo3en la ronda2con un costo de8.(2, 3), 0, 6: Si el equipo2juega contra el equipo3en la ronda0con un costo de6.(2, 3), 1, 9: Si el equipo2juega contra el equipo3en la ronda1con un costo de9.(2, 3), 2, 4: Si el equipo2juega contra el equipo3en la ronda2con un costo de4.
- Cantidad de Equipos: Asegúrate de que la cantidad de equipos sea un numero par.
- Rondas: El número de rondas debe ser
n-1dondenes el número de equipos. - Costos: Los costos son arbitrarios y pueden ajustarse según las necesidades del problema.
pip install -r requirements.txtPara ejecutar el script, utiliza el siguiente comando en la terminal. Asegúrate de especificar el archivo de configuración adecuado y los parámetros necesarios:
python main.py --variant traditional --entera True --file example.srr