Publicaciones en Ciencias y Tecnología (Dec 2013)
UNA FORMULACIÓN COMBINATORIA PARA EL PROBLEMA DE ASIGNACIÓN LOCAL-VISITANTE // A COMBINATORIAL OPTIMIZATION FORMULATION FOR THE HOME AWAY ASSIGNMENT PROBLEM
Abstract
The sports scheduling problem has been center of attention in the Operational Research community due to their variety of models, and computational complexity of solutions (see for example Ribeiro (2010)). In a Round Robin tournament, the schedule is proposed by assigning a “home" or “away" labels to a preestablished itinerary, in a such way that the total distance traveled by the teams during the tournament is minimized. In terms of operation research, the problem is modeled as a binary quadratic programming problem with linear constraints. In Suzuka y cols. (2005) the problem is treated as a MIN-RES-CUT. In this work we study the structure of the home-away assignment problem, and propose a simplification of the combinatorial formulation. We solve exactly small instances of the problem with an exhaustive search, and also approximately solve larger instances with a random search. // RESUMEN El problema de elaboración de calendarios deportivos ha centrado la atención de la comunidad de investigación de operaciones por la variedad de modelos y la complejidad computacional de las soluciones (ver por ejemplo Ribeiro (2010)). En torneos tipo Round Robin de ida y vuelta el calendario se propone asignando la etiqueta de local o visitante a cada equipo, en un itinerario preestablecido de manera que se minimice el recorrido total de los equipos durante el torneo. En términos de investigación de operaciones lo modelamos como un problema de optimización cuadrática binaria con restricciones lineales. Suzuka, Miyashiro, Yoshise, y Matsui (2005) lo tratan como uno de encontrar el corte mínimo con restricciones (Min-Res-Cut) en un grafo no dirigido, proporcionando una formulación de optimización combinatoria. En el presente trabajo estudiamos la estructura del problema de asignación local-visitante, y proponemos una simplificación de la formulación de optimización combinatoria. Resolvemos de forma exacta con una búsqueda exhaustiva instancias pequeñas del problema, y resolvemos de forma aproximada con una búsqueda aleatoria instancias mayores.
