Formulations and algorithms to design communication networks
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Tese de doutorado
Título alternativo
Primeiro orientador
Membros da banca
Alexandre Salles da Cunha
Mauricio Cardoso de Souza
Nelson Maculan Filho
Mauricio Cardoso de Souza
Nelson Maculan Filho
Resumo
O estudo de redes tem raízes na teoria dos grafos que remota a 1730. Desde então, redes vem tem sido utilizadas para modelar e simular interações entre elementos de sistemas complexos, tais como de transporte, de comunicação e de computadores. Redes de comunicação são amplamente utilizadas para trocar informações entre entidades de um sistema. A importância das redes de comunicação aumentou dramaticamente nos últimos anos, chamando atenção para o estágio de projeto de um sistema real, dando origem a diversos problemas de otimização. Técnicas e soluções de Pesquisa Operacional tem desempenhado papel fundamental sobre uma vasta gama de problemas de projeto de redes. Nesta tese, nós estudamos como aplicar técnicas de otimização no projeto de redes de comunicação. Primeiramente, nós abordamos o problema de projetar redes de telecomunicações hierárquicas assegurando resiliência contra falhas aleatórias e garantias de atraso na comunicação. Posteriormente, nós estudamos como projetar redes de comunicação eficientes com base em características de redes complexas. Um conjunto de métricas é usado como critério de otimização no projeto dessas redes. Finalmente, nós investigamos soluções para o problema de roteamento e alocação de comprimentos de onda com agregação de tráfego, proteção e qualidade de serviço em redes ópticas WDM. Diferentes formulações matemáticas para modelar os três problemas são propostas. Um algoritmo Branch-and-bound baseado nas formulações compactas é avaliado e comparado a uma abordagem Branch-and-price baseada nas formulações estendidas dos problemas. Uma análise comparativa é realizada, demonstrando que a abordagem Branch-and-Price proposta é capaz de resolver problemas cujas dimensões estão fora do alcance de outras ferramentas tradicionais de otimização.
Abstract
The study of networks has roots in graph theory dating back to 1730s. From then on, networks have been used to model and simulate interactions among elements of intricate systems, such as transportation, communication and computer ones. Communication networks are widely used to exchange information among entities of a system. The importance of communication networks has dramatically increased over the past few years, drawing attention to the design stage of a real system, giving rise to many optimization problems. Operations Research techniques and solutions have been playing a fundamental role across a wide range of network design problems. In this thesis, we study how to apply optimization techniques in the design of communication networks. Firstly, we dedicate to the problem of designing hierarchical telecommunication networks ensuring resilience against random failures and maximum delay guarantees in the communication. After, we study how to design efficient communication networks based on complex networks features. A set of metrics is used as optimization criteria while designing such networks. Finally, we investigate solutions to the routing and wavelength assignment problem with traffic grooming, protection and quality of service on WDM optical networks. Different mathematical formulations to model the three problems are proposed. A Branch-and-bound algorithm based on compact formulations is evaluated and compared to a Branch-and-price approach based on extended formulations of the problems. Our comparative analysis demonstrates that the proposed Branch-and-price approach is able to solve problems whose dimensions are out of reach for other traditional optimization tools.
Assunto
Computação
Palavras-chave
Programação inteira, Redes de comunicação