Modelos de programación lineal entera para el survivable routing and spectrum assignment problem with path protection

  • Flavia Bonomoa
  • Juan Pablo Lebona
  • Javier Leonardo Marenco Universidad Torcuato Di Tella
Palabras clave: rsa, programación entera

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.

Publicado
2023-07-11
Cómo citar
Bonomoa, F., Lebona, J., & Marenco, J. (2023). Modelos de programación lineal entera para el survivable routing and spectrum assignment problem with path protection. Memorias De Las JAIIO, 9(15), 165-165. Recuperado a partir de https://publicaciones.sadio.org.ar/index.php/JAIIO/article/view/542
Sección
SIIIO - Simposio Argentino de Informática Industrial e Investigación Operat