Árvores de Diâmetro Mínimo Sujeitas a Restrição de Orçamento
Autores
|
6935 |
3089,519
|
|
|
6936 |
3089,519
|
Informações:
Publicações do PESC
Dado um grafo não direcionado G = (V, E), investigamos três problemas que demandam árvores de G de diâmetro mínimo. A definição de diâmetro aqui utilizada é a usual, correspondendo, para uma árvore T = (VT , ET ) de G, ao número de arestas no caminho de T contendo omaior número delas. Para qualquer um dos três problemas, custos são associados às arestas de G e uma restrição de orçamento se aplica ao valor máximo permitido para a soma dos custos das arestas de uma árvore. No primeiro problema, o Budget Minimum Diameter Spanning Tree Problem, as árvores devem ser necessariamente geradoras. No segundo, o Budget Minimum Diameter Steiner Tree Problem, vértices obrigatórios, S ? V , são identificados de antemão e devem, necessariamente, fazer parte da solução. Esta, por sua vez, pode ser geradora ou não. Finalmente, o terceiro problema, o Budget Minimum Diameter Terminal Steiner Tree Problem, difere do segundo ao impor uma relação biunívoca entre as folhas de uma árvore viável e os vértices de S. Introduzimos o que nos parecem ser as primeiras formulações matemáticas propostas para qualquer um dos três problemas. Três formulações por problema. Feito isto, utilizamos os algoritmos de enumeração implícita do software Gurobi para resolvê-las de forma exata. Ainda pouco investigados na literatura, qualquer um dos três problemas tem um grande potencial de aplicação prática, particularmente no desenho de redes de telecomunicações. Além disso, se mostraram intrinsecamente interessantes e desafiadores, tanto em termos de modelagem quanto de algoritmos de solução.
Given an undirected graph G = (V, E), we investigate three problems seeking minimum diameter trees of G. The definition used for the diameter of a tree, T = (VT , ET ), is the usual one. Namely, the number of edges in the path of T that contains the largest number of them. For any of the three problems, costs are associated with the edges of G and the sum of the edge costs of a tree may not exceed a given budget value. For the first problem, the Budget Minimum Diameter Spanning Tree Problem, feasible trees must necessarily be spanning. For the second, the Budget Minimum Diameter Steiner Tree Problem, terminal vertices S ? V are identified beforehand and must be part of any feasible tree. These trees, in turn, may be spanning or not. Finally, the third problem, the Budget Minimum Diameter Terminal Steiner Tree Problem, differs from the previous one in that it imposes a one-to-one relation between leaves of a tree and vertices of S. We propose what apparently are the very first formulations for any of the three problems. Three formulations for every problem. Next, we rely on the implicit enumeration algorithms of the solver Gurobi to obtain proven optimal solutions for any of them. Barely investigated in the literature, any of the three problems have practical application potential, particularly in the design of telecommunication networks. Additionally, they proved to be intrinsically interesting and defying, both in modelling and algorithmic terms.