In this work we address the Optimal Communication Spanning Tree (OCST) problem. An instance of this problem consists of a tuple (G, c, R, w) composed of a connected graph G = (V, E), a nonnegative cost function c defined on E, a set R of pairs of vertices in V , and a nonnegative function w, called demand, defined on R. Each pair (u, v) of R is called a requirement, the vertex u is called origin, and the vertex v is called destination of the pair. For a given spanning tree T of G, the communication cost of a requirement pair r = (u, v) is defined as the demand w(r) multiplied by the distance between u and v in T (the distance being the sum of the costs of the edges in the path from u to v). In the Optimal Communication Spanning Tree (OCST) problem, we are given an instance (G, c, R, w) and we seek a spanning tree in G that minimizes the overall sum of the communication costs of all requirements in R. This problem was introduced by T. C. Hu in 1974 and is known to be NP-hard. Some of its special cases, not so trivial, can be solved in polynomial time. We address two such special cases of the OCST problem, both restricted to complete graphs. The first one is the Optimum Requirement Spanning Tree (ORST) problem, in which all edges have the same cost (a constant). In this case, an optimal solution is given by a Gomory-Hu tree of a certain associated network. The second one is a special case of the OCST problem, in which all requirements have the same demand. This problem is called Minimum Routing Cost Spanning tree (MRCT) (and is also known as the Optimum Distance Spanning Tree problem). We also study the main mixed integer linear programming (MILP) formulations for the OCST problem. For that, we first study formulations for the spanning tree problem, some purely combinatorial and some based on flows (leading to mixed formulations). Furthermore, we exhibit the computational results of the experiments we conducted with our implementation of a branch-and-cut approach for the different MILP formulations that we studied.

Neste trabalho estudamos o problema da Árvore Geradora de Comunicação Ótima (AGCO). Uma instância deste problema consiste de uma quádrupla (G, c, R, w) composta por um grafo conexo G = (V, E), uma função não-negativa c que atribui a cada elemento e E um custo c(e), um conjunto R de pares de vértices em V , e uma função não-negativa w, chamada demanda, definida sobre R. Cada par (u, v) de R é chamado um requisito, o vértice u é chamado origem e o vértice v é chamado destino do par. Para uma dada árvore geradora T de G, o custo de comunicação de um requisito r = (u, v) é definido como a demanda w(r) multiplicada pela distância entre u e v em T (sendo a distância a soma dos custos das arestas no caminho de u a v em T). No problema da Árvore Geradora de Comunicação Ótima, dada uma instância (G, c, R, w), o objetivo é encontrar em G uma árvore geradora que minimiza a soma total dos custos de comunicação de todos os requisitos em R. Este problema foi introduzido por T. C. Hu em 1974 e é sabido ser NP-difícil. Alguns de seus casos especiais, não tão triviais, podem ser resolvidos em tempo polinomial. Investigamos aqui dois tais casos especiais do problema AGCO, ambos para o caso de G ser um grafo completo. No primeiro deles, todas as arestas do grafo têm o mesmo custo. Neste caso, a solução é dada pela árvore de Gomory-Hu de uma certa rede associada à instância dada. No segundo problema, todos os requisitos têm a mesma demanda, e a solução é dada por uma árvore que é uma estrela. Também estudamos algumas formulações lineares inteiras mistas para o problema AGCO. Para isso, estudamos formulações lineares para o problema da árvore geradora mínima, algumas das quais fazem uso de fluxos. Tais formulações são combinadas e dão origem a algumas formulações mistas para o problema AGCO. Implementamos algoritmos branchand-cut para tais formulações, e apresentamos os resultados computacionais obtidos.