Un algoritmo branch-and-cut para el routing and spectrum allocation problem

Mostrar todas las versiones(3)

La fibra óptica flexible y en particular la tecnología llamada grilla flexible (flexgrid), especificada en el estándar ITU-T G.694.1, es una de las soluciones más prometedoras para lidiar con el enorme crecimiento del tráfico en redes muy grandes. En dicha especificación, el espectro de frecuencia d...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Bianchetti, Marcelo Luis
Formato: Tesis Doctoral
Lenguaje:Español
Publicado: 1 de
Materias:
PROGRAMACION LINEAL ENTERA
INVESTIGACION OPERATIVA
REDES DE FIBRA OPTICA
DESIGUALDADES VALIDAS
HEURISTICAS INICIALES
INTEGER LINEAR PROGRAMMING
OPERATIONAL RESEARCH
OPTICAL FIBER NETWORKS
VALID INEQUALITIES
INITIAL HEURISTICS
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n7196_Bianchetti
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:tesis_n7196_Bianchetti
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 PROGRAMACION LINEAL ENTERA
INVESTIGACION OPERATIVA
REDES DE FIBRA OPTICA
DESIGUALDADES VALIDAS
HEURISTICAS INICIALES
INTEGER LINEAR PROGRAMMING
OPERATIONAL RESEARCH
OPTICAL FIBER NETWORKS
VALID INEQUALITIES
INITIAL HEURISTICS
spellingShingle PROGRAMACION LINEAL ENTERA
INVESTIGACION OPERATIVA
REDES DE FIBRA OPTICA
DESIGUALDADES VALIDAS
HEURISTICAS INICIALES
INTEGER LINEAR PROGRAMMING
OPERATIONAL RESEARCH
OPTICAL FIBER NETWORKS
VALID INEQUALITIES
INITIAL HEURISTICS
Bianchetti, Marcelo Luis
Un algoritmo branch-and-cut para el routing and spectrum allocation problem
topic_facet PROGRAMACION LINEAL ENTERA
INVESTIGACION OPERATIVA
REDES DE FIBRA OPTICA
DESIGUALDADES VALIDAS
HEURISTICAS INICIALES
INTEGER LINEAR PROGRAMMING
OPERATIONAL RESEARCH
OPTICAL FIBER NETWORKS
VALID INEQUALITIES
INITIAL HEURISTICS
description La fibra óptica flexible y en particular la tecnología llamada grilla flexible (flexgrid), especificada en el estándar ITU-T G.694.1, es una de las soluciones más prometedoras para lidiar con el enorme crecimiento del tráfico en redes muy grandes. En dicha especificación, el espectro de frecuencia de un cable de fibra óptica es dividido en canales más angostos, denominados slots. Cualquier secuencia consecutiva de slots puede ser usada como un solo canal. A la conexión que utiliza dicho canal a largo de una ruta a través de los nodos de la red se la denomina lightpath. Dado un conjunto de demandas punto-a-punto, al problema de establecer los lightpaths para satisfacerlas se denomina problema de Ruteo y Asignación de Espectro (RSA). Dada su relevancia, este problema ha sido estudiado intensivamente en la última década. Se demostró que pertenece a la clase NP-difícil, y en la práctica se comprobó que es necesario aplicar técnicas computacionales no triviales para obtener soluciones de instancias reales. En la última década, aplicando técnicas de programación entera se ha logrado resolver bien en la práctica una gran cantidad de problemas de optimización combinatoria. El principal objeto del presente trabajo es ampliar dicho campo, mediante la aplicación de técnicas de programación lineal entera sobre el RSA. El primer paso es explorar varios modelos de programación lineal entera para el RSA, analizando su efectividad en instancias conocidas. Recurrimos a varias técnicas de modelado, con el fin de encontrar formulaciones naturales de este problema. Una vez comparados estos modelos, analizamos en profundidad uno de los más prometedores para comprender sus características, fortalezas y debilidades, teniendo en cuenta sus propiedades combinatorias. A partir de los resultados de dicho estudio, desarrollamos procedimientos computacionales basados en programación lineal entera para el RSA, incluyendo el uso de planos de corte y heurísticas primales, con el objetivo final de resolver de manera óptima o casi óptima instancias reales de este problema. Este trabajo también contiene el desarrollo de un generador de instancias basado en topologías reales, y la compilación bibliográfica más extensa hasta la fecha enumerando y clasificando los trabajos que tratan el RSA y sus variaciones más cercanas desde la óptica de la optimización combinatoria [fórmula aproximada, revisar la misma en el original].
format Tesis Doctoral
author Bianchetti, Marcelo Luis
author_facet Bianchetti, Marcelo Luis
author_sort Bianchetti, Marcelo Luis
title Un algoritmo branch-and-cut para el routing and spectrum allocation problem
title_short Un algoritmo branch-and-cut para el routing and spectrum allocation problem
title_full Un algoritmo branch-and-cut para el routing and spectrum allocation problem
title_fullStr Un algoritmo branch-and-cut para el routing and spectrum allocation problem
title_full_unstemmed Un algoritmo branch-and-cut para el routing and spectrum allocation problem
title_sort un algoritmo branch-and-cut para el routing and spectrum allocation problem
publishDate 1 de
url https://hdl.handle.net/20.500.12110/tesis_n7196_Bianchetti
work_keys_str_mv AT bianchettimarceloluis unalgoritmobranchandcutparaelroutingandspectrumallocationproblem
AT bianchettimarceloluis abranchandcutalgorithmfortheroutingandspectrumallocationproblem
_version_ 1782030822045384704
spelling todo:tesis_n7196_Bianchetti2023-10-03T13:17:03Z Un algoritmo branch-and-cut para el routing and spectrum allocation problem A branch and cut algorithm for the routing and spectrum allocation problem Bianchetti, Marcelo Luis PROGRAMACION LINEAL ENTERA INVESTIGACION OPERATIVA REDES DE FIBRA OPTICA DESIGUALDADES VALIDAS HEURISTICAS INICIALES INTEGER LINEAR PROGRAMMING OPERATIONAL RESEARCH OPTICAL FIBER NETWORKS VALID INEQUALITIES INITIAL HEURISTICS La fibra óptica flexible y en particular la tecnología llamada grilla flexible (flexgrid), especificada en el estándar ITU-T G.694.1, es una de las soluciones más prometedoras para lidiar con el enorme crecimiento del tráfico en redes muy grandes. En dicha especificación, el espectro de frecuencia de un cable de fibra óptica es dividido en canales más angostos, denominados slots. Cualquier secuencia consecutiva de slots puede ser usada como un solo canal. A la conexión que utiliza dicho canal a largo de una ruta a través de los nodos de la red se la denomina lightpath. Dado un conjunto de demandas punto-a-punto, al problema de establecer los lightpaths para satisfacerlas se denomina problema de Ruteo y Asignación de Espectro (RSA). Dada su relevancia, este problema ha sido estudiado intensivamente en la última década. Se demostró que pertenece a la clase NP-difícil, y en la práctica se comprobó que es necesario aplicar técnicas computacionales no triviales para obtener soluciones de instancias reales. En la última década, aplicando técnicas de programación entera se ha logrado resolver bien en la práctica una gran cantidad de problemas de optimización combinatoria. El principal objeto del presente trabajo es ampliar dicho campo, mediante la aplicación de técnicas de programación lineal entera sobre el RSA. El primer paso es explorar varios modelos de programación lineal entera para el RSA, analizando su efectividad en instancias conocidas. Recurrimos a varias técnicas de modelado, con el fin de encontrar formulaciones naturales de este problema. Una vez comparados estos modelos, analizamos en profundidad uno de los más prometedores para comprender sus características, fortalezas y debilidades, teniendo en cuenta sus propiedades combinatorias. A partir de los resultados de dicho estudio, desarrollamos procedimientos computacionales basados en programación lineal entera para el RSA, incluyendo el uso de planos de corte y heurísticas primales, con el objetivo final de resolver de manera óptima o casi óptima instancias reales de este problema. Este trabajo también contiene el desarrollo de un generador de instancias basado en topologías reales, y la compilación bibliográfica más extensa hasta la fecha enumerando y clasificando los trabajos que tratan el RSA y sus variaciones más cercanas desde la óptica de la optimización combinatoria [fórmula aproximada, revisar la misma en el original]. One of the most promising solutions to deal with huge data traffic demands in large communication networks is given by flexible optical networking, in particular the flexible grid (flexgrid) technology specified in the ITU-T standard G.694.1. In this specification, the frequency spectrum of an optical fiber link is divided into narrow frequency slots. Any sequence of consecutive slots can be used as a simple channel, and such a channel can be switched in the network nodes to create a lightpath. In this kind of networks, the problem of establishing lightpaths for a set of end-to-end demands that compete for spectrum resources is called the Routing and Spectrum Allocation problem (RSA). Due to its relevance, this problem has been intensively studied in the last decade. It has been shown to be NP-hard, and nontrivial computational techniques are to be applied in order to tackle the solution of practical instances. Since integer programming techniques are known to provide successful practical approaches for several combinatorial optimization problems, the aim of this work is to further the exploration of such an issue, by applying integer linear programming techniques to RSA. The first objective is to explore several integer programming models for RSA, analyzing their effectiveness over known instances. We resort to several modeling techniques in order to find natural formulations of this problem. Having compared these models, then we make a detailed analysis of one of the most promising of them in order to understand its properties, strengths, and weaknesses, taking combinatorial properties into account. Based on these explorations, we develop integer linear programming based computational procedures for RSA including the use of cutting planes and primal heuristics, with the final objective of solving to optimality or near-optimality real-world instances of RSA. This work also contains the development of an instance generator based on real topologies, and the most extensive survey to date listing and classifying the works that treat the RSA and its closest variations from the point of view of combinatorial optimization [fórmula aproximada, revisar la misma en el original]. Fil: Bianchetti, Marcelo Luis. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 1 de septiembre de 2022 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_n7196_Bianchetti

Ejemplares similares