Modelos de programación lineal entera para el survivable routing and spectrum assignment problem with path protection
Resumen
El routing and spectrum assignment (RSA) problem surge el la planificación de redes de fibra óptica, y consiste en establecer los lightpaths para un conjunto de demandas de tráfico, cada una de las cuales está expresada en términos de un nodo de origen, un nodo de destino y una cantidad de slots. Cada lightpath está determinado por una ruta y un canal, y el RSA consiste en encontrar una ruta y asignar un intervalo de slots para cada demanda. El survivable RSA with path protection es una variante de RSA, que corresponde a solicitar dos lightpaths para cada demanda: un camino titular y un camino de backup, que respeten las restricciones de RSA y que usen el mismo conjunto de slots. Este problema es NP-hard.
En este trabajo se proponen distintos modelos de programación lineal entera para este problema, y se estudia su performance en la práctica sobre topologías reales. Se presentan además familias de desigualdades válidas para una de estas formulaciones, y se estudia su impacto en la resolución computacional de esta formulación.
