Sobre o Projeto

Os problemas de projeto de topologias virtuais e roteamento de tráfego em redes ópticas podem ser representados de maneira exata por modelos de programação linear mista. Tais modelos de otimização combinatorial são de difícil tratamento computacional, requerendo a utilização de técnicas de redução do espaço de busca e métodos aproximados, ou heurísticas, com menor custo computacional, normalmente em detrimento da qualidade da solução obtida. Este trabalho estudará heurísticas, formulações de programação linear e de programação linear inteira-mista com o propósito de estudar sua eficiência em termos de duas métricas importantes para a avaliação da qualidade da solução obtida para os sub-problemas abordados, que são o congestionamento e o processamento eletrônico de tráfego nos nós. Para serem consideradas eficientes, os métodos estudados deverão proporcionar pelo menos boas soluções para estas métricas com esforço computacional razoável. Uma solução é considerada boa quando se aproxima de um limite inferior teórico ou de uma solução ótima conhecidos, que deverão ser coletados da bibliografia disponível ou então determinados nos estudos desenvolvidos neste projeto, segundo cada caso. A qualidade da solução de uma heurística considerada eficiente não poderá depender das demandas de tráfego entre os nós da rede, sendo tal avaliação realizada em um estudo estatístico num espaço amostral com diversas matrizes de tráfego geradas aleatoriamente. O objetivo geral deste projeto é propor formulações de programação matemática e métodos heurísticos eficientes para os sub-problemas de projeto de topologias lógicas e roteamento de tráfego, chegando a soluções próximas de limites teóricos conhecidos com reduzido esforço computacional. Os objetivos específicos são: a) Avaliar as soluções obtidas para o roteamento de tráfego em termos de congestionamento e processamento de tráfego nos nós; b) Investigar qual é a eficiência das diversas heurísticas e formulações de prog