Un algoritmo branch-and-cut para el routing and spectrum allocation problem

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2022-09-01

Tipo de documento: 

info:eu-repo/semantics/doctoralThesis
 

Formato:

application/pdf

Idioma:

spa

Temas:

PROGRAMACION LINEAL ENTERA - INVESTIGACION OPERATIVA - REDES DE FIBRA OPTICA - DESIGUALDADES VALIDAS - HEURISTICAS INICIALES - INTEGER LINEAR PROGRAMMING - OPERATIONAL RESEARCH - OPTICAL FIBER NETWORKS - VALID INEQUALITIES - INITIAL HEURISTICS

Descripción:

La fibra óptica flexible y en particular la tecnología llamada grilla flexible (flexgrid), especificada en el estándar ITU-T G.694.1, es una de las soluciones más prometedoras para lidiar con el enorme crecimiento del tráfico en redes muy grandes. En dicha especificación, el espectro de frecuencia de un cable de fibra óptica es dividido en canales más angostos, denominados slots. Cualquier secuencia consecutiva de slots puede ser usada como un solo canal. A la conexión que utiliza dicho canal a largo de una ruta a través de los nodos de la red se la denomina lightpath. Dado un conjunto de demandas punto-a-punto, al problema de establecer los lightpaths para satisfacerlas se denomina problema de Ruteo y Asignación de Espectro (RSA). Dada su relevancia, este problema ha sido estudiado intensivamente en la última década. Se demostró que pertenece a la clase NP-difícil, y en la práctica se comprobó que es necesario aplicar técnicas computacionales no triviales para obtener soluciones de instancias reales. En la última década, aplicando técnicas de programación entera se ha logrado resolver bien en la práctica una gran cantidad de problemas de optimización combinatoria. El principal objeto del presente trabajo es ampliar dicho campo, mediante la aplicación de técnicas de programación lineal entera sobre el RSA. El primer paso es explorar varios modelos de programación lineal entera para el RSA, analizando su efectividad en instancias conocidas. Recurrimos a varias técnicas de modelado, con el fin de encontrar formulaciones naturales de este problema. Una vez comparados estos modelos, analizamos en profundidad uno de los más prometedores para comprender sus características, fortalezas y debilidades, teniendo en cuenta sus propiedades combinatorias. A partir de los resultados de dicho estudio, desarrollamos procedimientos computacionales basados en programación lineal entera para el RSA, incluyendo el uso de planos de corte y heurísticas primales, con el objetivo final de resolver de manera óptima o casi óptima instancias reales de este problema. Este trabajo también contiene el desarrollo de un generador de instancias basado en topologías reales, y la compilación bibliográfica más extensa hasta la fecha enumerando y clasificando los trabajos que tratan el RSA y sus variaciones más cercanas desde la óptica de la optimización combinatoria [fórmula aproximada, revisar la misma en el original].

Identificador:

https://hdl.handle.net/20.500.12110/tesis_n7196_Bianchetti