Árvore de suporte de custo mínimo com restrições de salto

Abstract

Neste trabalho descrevemos um algoritmo Dual Ascendente para o problema da Árvore de Suporte de Custo Mínimo com Restrições de Salto (HMST). O problema HMST modela o desenho de uma rede de telecomunicações centralizada com restrições de salto. Estas restrições estão relacionadas com a performance da rede, uma vez que limitam o número de ligações que podem ser utilizadas para ligar o computador central a qualquer um dos terminais e garantem uma certa qualidade de serviço no que diz respeito a alguns critérios de performance tais como disponibilidade, fiabilidade e tempos de atraso máximo de transmissão. Apresentamos duas formulações de fluxos orientadas já apresentadas para este problema. A primeira obtém-se de uma conhecida formulação de fluxos para o problema da Árvore de Suporte de Custo Mínimo adicionando as restrições de salto e a segunda é uma formulação que usa índices de salto, é mais compacta, e foi obtida por Gouveia utilizando a técnica de redefinição de variáveis de Martin. Como o problema é NP-difícil centrámos a nossa atenção na obtenção de um Algoritmo Dual Ascendente para obter um limite inferior para o valor óptimo deste problema e construímos uma heurística baseada na solução Dual Ascendente que nos permitiu obter um limite superior. A técnica Dual Ascendente consiste, essencialmente, numa forma de resolução do problema dual (ou da relaxação lagrangeana ou da relaxação linear) que tira vantagem da estrutura especial que o problema dual tem. Os resultados computacionais que apresentamos para avaliar a qualidade dos valores obtidos indicam que, apesar do algoritmo Dual Ascendente e da heurística baseada na solução dual ascendente permitirem de uma forma muito rápida obter, respectivamente, um limite inferior e um limite superior para o valor óptimo do problema, estes limites são de fraca qualidade.

ABSTRACT: In this thesis we describe a Dual Ascent algorithm to the Hop-Constrained Minimum Spanning Tree Problem (HMST). This problem models the design of centralized telecommunication network with hop constraints. These restrictions are related to the network performance. They limit the number of connections that can be used to link the central computer to any of the terminals and they guarantee a certain quality of service with respect to some performance constraints such as availability, reliability and the maximum transmission delay. We present two direct flow formulations already presented for this problem. The first one is obtained from a known flow formulation for the Minimum Spanning Tree Problem adding hop constraints and the second one is a formulation which uses hop-indexes, is more compact and it was obtained by Gouveia using the variable redefinition technique of Martin. As the problem is NP-hard we focus our attention on obtaining a Dual Ascent Algorithm to get to a lower bound to the optimal value of this problem and we build a heuristic based on the dual ascent solution which made it possible to get an upper bound. The Dual Ascent method consists essentially on a way to solve the dual problem (or from the lagrangean relaxation or from the linear relaxation) which takes advantage from the special structure of the dual problem. The computational results we present to evaluate the quality of the obtained values indicate that, although the algorithm Dual Ascent and the heuristic based on the dual ascent solution allow us to obtain in a very rapid way, respectively, a lower and an upper bound for the optimal value of the problem, these bounds are very poor.