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

Mostrar todas las versiones(3)

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 mej...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Delgadillo Cárdenas, Remberto Emanuel
Formato: Tesis Doctoral
Lenguaje:Español
Publicado: 2021
Materias:
P-CICLOS
REDES SUPERVIVIENTES
PROGRAMACION LINEAL ENTERA
GENERACION DE COLUMNAS
HEURISTICAS
P-CYCLES
SURVIVABLE NETWORKS
INTEGER LINEAR PROGRAMMING
COLUMN GENERATION
HEURISTICS
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n7006_DelgadilloCardenas
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:tesis_n7006_DelgadilloCardenas
record_format dspace
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Español
orig_language_str_mv Español
topic P-CICLOS
REDES SUPERVIVIENTES
PROGRAMACION LINEAL ENTERA
GENERACION DE COLUMNAS
HEURISTICAS
P-CYCLES
SURVIVABLE NETWORKS
INTEGER LINEAR PROGRAMMING
COLUMN GENERATION
HEURISTICS
spellingShingle P-CICLOS
REDES SUPERVIVIENTES
PROGRAMACION LINEAL ENTERA
GENERACION DE COLUMNAS
HEURISTICAS
P-CYCLES
SURVIVABLE NETWORKS
INTEGER LINEAR PROGRAMMING
COLUMN GENERATION
HEURISTICS
Delgadillo Cárdenas, Remberto Emanuel
Un algoritmo branch-and-price-and-cut para diseño de redes con p-ciclos
topic_facet P-CICLOS
REDES SUPERVIVIENTES
PROGRAMACION LINEAL ENTERA
GENERACION DE COLUMNAS
HEURISTICAS
P-CYCLES
SURVIVABLE NETWORKS
INTEGER LINEAR PROGRAMMING
COLUMN GENERATION
HEURISTICS
description 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.
format Tesis Doctoral
author Delgadillo Cárdenas, Remberto Emanuel
author_facet Delgadillo Cárdenas, Remberto Emanuel
author_sort Delgadillo Cárdenas, Remberto Emanuel
title Un algoritmo branch-and-price-and-cut para diseño de redes con p-ciclos
title_short Un algoritmo branch-and-price-and-cut para diseño de redes con p-ciclos
title_full Un algoritmo branch-and-price-and-cut para diseño de redes con p-ciclos
title_fullStr Un algoritmo branch-and-price-and-cut para diseño de redes con p-ciclos
title_full_unstemmed Un algoritmo branch-and-price-and-cut para diseño de redes con p-ciclos
title_sort un algoritmo branch-and-price-and-cut para diseño de redes con p-ciclos
publishDate 2021
url https://hdl.handle.net/20.500.12110/tesis_n7006_DelgadilloCardenas
work_keys_str_mv AT delgadillocardenasrembertoemanuel unalgoritmobranchandpriceandcutparadisenoderedesconpciclos
AT delgadillocardenasrembertoemanuel abranchandpriceandcutalgorithmforpcyclenetworkdesign
_version_ 1782027694741913600
spelling todo:tesis_n7006_DelgadilloCardenas2023-10-03T13:15:18Z Un algoritmo branch-and-price-and-cut para diseño de redes con p-ciclos A branch-and-price-and-cut algorithm for p-cycle network design Delgadillo Cárdenas, Remberto Emanuel P-CICLOS REDES SUPERVIVIENTES PROGRAMACION LINEAL ENTERA GENERACION DE COLUMNAS HEURISTICAS P-CYCLES SURVIVABLE NETWORKS INTEGER LINEAR PROGRAMMING COLUMN GENERATION HEURISTICS 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. The p-cycle networking concept was introduced in the late 90’s in the context of survivable optical networks. A communication network is said to be survivable if it keeps operating although any of its components fails. P-cycles based topologies gather the best features to ensure survivability: restoration speed and low spare capacity, which implies a low cost. A p-cycle is a preconfigured cycle composed of a single channel of spare capacity on each link it crosses. Each p-cycle protects all the links that belong to the cycle and also each link that is not part of the cycle but its two end nodes are. Due to the necessity of designing p-cycle networks of minimum cost, several combinatorial optimization problems were defined. The basic problem of those is the Spare Capacity Allocation problem - SCA. Its input has a network with previously assigned working demands associated to each link. The goal is to organize the spare capacity of the network into a set of p-cycles so that communication restoration is guaranteed in case of any single link failure. Each additional spare link increases solution cost, that has to be minimized. We developed a branch-and-price-and-cut algorithm for SCA. We introduce a new MIP formulation for it, which has the typical diagonal block structure found in this kind of problems. We apply Dantzig-Wolfe decomposition to this formulation to get the Master Problem and the Pricing Problem. After decomposition, the symmetry issue due to the diagonal block structure is eliminated, although the Pricing Problem is shown to be N P-hard. We detail all modifications needed to apply branching rules and cutting planes on the Master Problem without modifying the Pricing Problem structure in most cases, and making little modifications in others. Pricing instances are solved by an exact algorithm (branch-and-cut), and we also introduce heuristics to finish the column generation process as early as possible. For computational experiments, we have a set of real-world network instances to compare our algorithm with previous works. We also generated larger instances to evaluate the introduced features of the algorithm. Results show that the developed branch-and-price-and-cut algorithm outperforms previously presented works found in literature for SCA. Fil: Delgadillo Cárdenas, Remberto Emanuel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2021 Tesis Doctoral PDF Español info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n7006_DelgadilloCardenas

Ejemplares similares