Obtenção de limites inferiores para problemas de desenho de redes

Abstract

Nesta tese descrevemos a técnica da relaxação lagrangeana e métodos para optimizar o problema dual lagrangeano. Descrevemos o método do subgradiente, o método do subgradiente radar e o método do feixe de subgradientes. Em particular apresentamos uma relaxação lagrangeana para o problema da Árvore de Suporte de Custo Mínimo com Restrições de Salto (HMST) e aplicamos alguns destes métodos à sua resolução. O problema HMST surge, por exemplo, em situações de desenho de redes de telecomunicações centralizadas com restrições de qualidade de serviço e consiste em determinar uma árvore de suporte de custo mínimo com a restrição adicional de o número de arestas no único caminho de um nodo central a qualquer outro nodo da árvore não ser superior a um determinado valor. Apresentamos, ainda alguns resultados computacionais obtidos com a aplicação de alguns dos métodos descritos para a obtenção de uma aproximação do valor da relaxação lagrangeana apresentada para o problema HMST.

ABSTRACT: In this thesis we describe the lagrangean relaxation technique and methods to optimize the lagrangean dual problem. We describe the subgradient method, the radar subgradient method and the bundle method. We present a lagrangean relaxation for the Hop-constrained minimum spanning tree problem (HMST) and use some of the described methods to solve this relaxation. The HMST appears in centralized network design problems where quality of service constraints are required and the problem is to determine a minimum spanning tree such that the length of the only path between the central node and any node in the tree is at most a certain value. We also present some computational results obtained when solving the lagrangean relaxation presented for the HMST using some the methods described.