Algoritmos exactos para el problema del Antibandwidth

Abstract

Los problemas de optimización se caracterizan por la búsqueda de un valor óptimo dentro del espacio de soluciones factibles, es decir, el valor de la mejor solución de entre todas las posibles. Para resolver este tipo de problemas existen programas genéricos (solvers) que, mediante una formulación matemática, son capaces de encontrar la solución óptima. También es posible la creación de programas específicos para resolver el problema. Dentro de los métodos específicos podemos distinguir entre técnicas aproximadas y exactas. Las técnicas aproximadas están basadas en heurísticas y son capaces de obtener soluciones de buena calidad en un tiempo limitado, pero sin poder certificar que dichas soluciones sean soluciones óptimas. Las técnicas exactas son aquellas que garantizan que la solución encontrada es la mejor posible, es decir, la solución óptima, aunque tienen el inconveniente de que invierten mucho tiempo en la ejecución. Dentro de los problemas de optimización, el problema del Antibandwidth, es un problema de maximización y, en base a la estructura de sus soluciones, un problema de permutaciones. El problema consiste en etiquetar los vértices de un grafo no dirigido y no ponderado, de forma que se maximice la diferencia mínima de etiquetas entre los vértices adyacentes. Las etiquetas se corresponden con el rango de valores [1..N], siendo N el número de vértices del grafo. Un vértice sólo puede tener una etiqueta y, una etiqueta sólo puede estar asignada a un único vértice. Entre las distintas aplicaciones del problema del Antibandwidth, una de las aplicaciones más relevantes es el reparto de frecuencias de radio a distintas emisoras. Las emisoras que están cerca geográficamente no pueden tener frecuencias muy parecidas, ya que esto generaría interferencias, por lo que se busca asignar frecuencias lo más distantes posibles a emisoras cercanas y frecuencias parecidas a emisoras que estén alejadas entre sí. El objetivo de este Proyecto de Fin de Carrera consiste en desarrollar un algoritmo exacto capaz de resolver el problema del Antibandwidth en un tiempo razonable, cuando el tamaño del mismo sea pequeño y, de dar cotas inferiores y superiores lo más ajustadas posibles, para problemas de mayor tamaño. Para ello se han propuesto diversos esquemas algorítmicos cuyo rendimiento será evaluado, comparando sus resultados con software comercial capaz de resolver este tipo de problemas, en concreto el solver CPLEX.