Disertación de Maestría
DOI
https://doi.org/10.11606/D.45.2021.tde-10032022-204719
Documento
Autor
Nombre completo
Jainor Nestor Cardenas Choque
Dirección Electrónica
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2021
Director
Tribunal
Wakabayashi, Yoshiko (Presidente)
Moura, Phablo Fernando Soares
Usberti, Fabio Luiz

Título en inglés
Optimal Communication Spanning Tree
Resumen en inglés
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.

Título en portugués
Palabras clave en portugués
Árvore GomoryHu
Branch-and-cut
Programação linear inteira
Resumen en portugués