Título: Un estudio poliedral del routing and spectrum allocation problem
Director: Dr. Javier Marenco
Jurado: Dr. Cid de Souza (Mercado Libre, Argentina y Brasil)
Dr. Enrico Malaguti (Universidad de Bologna, Italia)
Dr. Juan José Salazar González (Universidad de la Laguna, España)

Transmisión en vivo: https://youtube.com/live/ORVcyv-XAfk?feature=share

Resumen:

El problema de ruteo y asignación de espectro (RSA) surge en el contexto de las redes de fibra óptica flexible y consiste en determinar rutas óptimas para un conjunto de demandas a través de una red, mientras de manera simultánea se asigna un intervalo del espectro electromagnético a cada demanda, sujeto a restricciones de no superposición. Como solución clave para gestionar el tráfico de datos a gran escala en dichas redes, el RSA ha ganado atención significativa, a pesar de ser un problema NP-difícil. Dado que la aplicación de técnicas de programación entera ha demostrado ser exitosa para varios problemas de optimización combinatoria, el objetivo principal de esta tesis es utilizarlas en el contexto del RSA. Comenzamos presentando varios modelos de programación entera para el problema y analizamos su efectividad. Basándonos en los resultados, definimos el politopo asociado a la formulación con mejor desempeño sobre instancias conocidas y presentamos un estudio poliedral del mismo, incluyendo su dimensión y familias de desigualdades que definen facetas. Luego de este estudio y dada la complejidad del problema, definimos una relajación de la formulación dada por un subconjunto de variables de la formulación original, con el fin de identificar desigualdades válidas que puedan ser útiles dentro de un entorno de métodos de planos de corte. Presentamos propiedades básicas de esta formulación relajada, identificamos varias familias de desigualdades que inducen facetas y mostramos que algunas de ellas pueden separarse en tiempo polinomial. Finalmente, incluimos experimentos computacionales que ofrecen indicios sobre la contribución de estas desigualdades en la práctica.