Modelos e Algoritmos de Programação Inteira no Projeto de Redes de Telecomunicações

Esta tese dá ênfase ao estudo dos problemas que surgem durante o projeto de redes de telecomunicações. Mais precisamente, estudaremos problemas que surgem no projeto de uma rede backbone. 0 primeiro problema, denominado Problema de Atribuição de Localidades a Anéis, caracteriza-se par ser um problema de particionamento de um grafo. São apresentadas e discutidas diferentes formulações de programação linear inteira para o problema. Investigamos a estrutura facial do poliedro associado ao problema e introduzimos novas famílias de facetas. Realizamos, ainda, um estudo sabre o problema de simetria entre as soluções do problema de atribuição de localidade a anéis. Por último, descrevemos os experimentos computacionais realizados com um algoritmo branch-and-price que propusemos neste trabalho. Através deste algoritmo foi possível resolver, de forma exata, instâncias com até 50 localidades. 0 segundo problema, denominado de Problema de Construção dos Anéis Idênticos, pode ser reduzido uma instância do Problema do Caixeiro Viajante Simétrico. Apresentamos alguns planos-de-corte, denominados planos-de-corte geométricos, que podem ser aplicados na resolução deste problema. Estabelecemos, ainda, uma relação entre estes planos-de-corte e os planos-de-corte canônicos. Em seguida, relatamos alguns resultados computacionais obtidos com o emprego do algoritmo cut-and-branch que propusemos, para resolver instâncias do problema do caixeiro viajante simétrico. 0 desempenho computacional deste algoritmo mostra a força dos planos-de-corte geométricos e, assim, a possibilidade do seu emprego na resolução de instâncias do problema de construção dos anéis idênticos.