Título: Un algoritmo branch-and-price and cut para diseño de redes con p-ciclos

Directora: Irene Loiseau

Jurados:

– Elena Fernández Aréizaga,Universidad de Cádiz, España.
– Celso Carneiro Ribeiro, Universidad Federal Fluminense, Brasil.
– Héctor Cancela, Universidad de la República, Uruguay.

Link a la transmisión por YouTube: https://youtu.be/LRA38dX81-o

———————————————————————————————————-

RESUMEN:

El concepto de redes de p-ciclos se introdujo a fines de los años 90 en el contexto de
redes ópticas supervivientes. Una red de comunicaciones se dice superviviente si puede
continuar brindando servicio pese a la falla de alguno de sus componentes. Las topologías
basadas en p-ciclos combinan las mejores características para asegurar la supervivencia:
velocidad en la recuperación y poca capacidad redundante, lo que implica menor costo.
Un p-ciclo es un ciclo preconfigurado formado por un canal de reserva en cada enlace que
lo compone. Cada p-ciclo protege a todos los enlaces que forman el ciclo y también a cada
enlace que no es parte del ciclo pero cuyos nodos s lo son.
A partir de la necesidad de diseñar redes basadas en p-ciclos de costo mínimo, surgieron
varios problemas de optimización combinatoria, de los cuales el mas elemental es el
problema de Asignación de Capacidad de Reserva (Spare Capacity Allocation – SCA). En
este problema se tiene una red con demandas asociadas a cada enlace previamente asignadas.
Se debe determinar la disposición de la capacidad de reserva mediante la ubicación
de p-ciclos de forma que quede garantizada la recuperación de las comunicaciones ante la
falla de alguno de sus enlaces. Cada enlace adicional de reserva incrementa el costo de la
solución, que debe ser minimizado.
En este trabajo desarrollamos un algoritmo branch-and-price-and-cut para SCA. Para
eso presentamos una nueva formulación como problema de programación lineal entera, la
cual que tiene una estructura diagonal en bloque usual en este tipo de problemas. A partir
de esta formulación aplicamos la descomposición Dantzig-Wolfe para obtener el problema
maestro y el problema de pricing. Con la descomposición eliminamos el inconveniente
de la simetría proveniente de la estructura diagonal de la formulación original, aunque
también mostramos que el problema de pricing resultante es NP-hard. Detallamos las
modificaciones necesarias que permiten aplicar reglas de branching y planos de corte en el
problema maestro sin modificar la estructura del problema de pricing en la mayoría de los
casos, y realizando modificaciones poco significativas en otros. Resolvemos las instancias
de pricing de forma exacta, y también proponemos heurísticas para esto, con el objetivo
de acelerar el proceso de generación de columnas.
Para la experimentación contamos con instancias correspondientes a redes reales para
comparar nuestro algoritmo con trabajos previos y generamos instancias mas grandes para
evaluar los distintos parámetros. Los resultados obtenidos mostraron ser muy superadores
respecto a trabajos anteriores para este problema.