Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.45.2021.tde-10032022-204719
Document
Auteur
Nom complet
Jainor Nestor Cardenas Choque
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2021
Directeur
Jury
Wakabayashi, Yoshiko (Président)
Moura, Phablo Fernando Soares
Usberti, Fabio Luiz
Titre en anglais
Optimal Communication Spanning Tree
Resumé en anglais
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.
Titre en portugais
Mots-clés en portugais
Árvore GomoryHu
Branch-and-cut
Programação linear inteira
Resumé en portugais