Problema do saco-mochila com estrutura em árvore

Abstract

Nesta dissertação, são apresentados alguns dos algoritmos exactos existentes que permitem resolver o Problema do Saco-mochila com Estrutura em Árvore (TKP) e, em particular, são apresentadas de forma uniforme e completa as técnicas de resolução do TKP recorrendo a algoritmos de programação dinâmica. Posteriormente, o TKP é reformulado e são desenvolvidas duas formulações (SP1 e SP2) deste problema como um Problema de Caminho Mais Curto com Restrições de Capacidade. Em seguida, são desenvolvidas duas formulações estendidas (SP3 e SP4) do TKP como um Problema de Caminho Mais Curto. Para comparar a eficiência destas duas últimas formulações, foi feita uma análise da sua implementação computacional considerando diferentes instâncias do problema. Os resultados mostram que a sua eficiência depende da topologia da árvore. Finalmente, é apresentada uma aplicação do TKP ao Desenho de Redes de Acesso Local de Telecomunicações (LANTD).

ABSTRACT: In this dissertation, we survey exact algorithms to solve the Tree Knapsack Problem (TKP) and, in particular, we provide a complete and unified presentation of dynamic programs. Then we present two distinct reformulations of the TKP (SP1 and SP2) as a Capacitated Shortest Path Problem. After that, we extend these formulations and develop another two models (SP3 and SP4) of TKP, as a Shortest Path Problem. In order to show the efficiency of the last two models we conduct a computational analysis that concern different problem instances. Our results show that the efficiency of these formulations depends from the tree topology. Finally, we present an application of the TKP to Local Access Network Telecommunications Design (LANTD).