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

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2021-11-10

Tipo de documento: 

info:eu-repo/semantics/doctoralThesis
 

Formato:

application/pdf

Idioma:

spa

Temas:

P-CICLOS - REDES SUPERVIVIENTES - PROGRAMACION LINEAL ENTERA - GENERACION DE COLUMNAS - HEURISTICAS - P-CYCLES - SURVIVABLE NETWORKS - INTEGER LINEAR PROGRAMMING - COLUMN GENERATION - HEURISTICS

Descripción:

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 más 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 instancia 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 más grandes para evaluar los distintos parámetros. Los resultados obtenidos mostraron ser muy superadores respecto a trabajos anteriores para este problema.

Identificador:

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