Formulações e algoritmos sequenciais e paralelos para o problema da árvore geradora de custo mínimo com restrição de grau mínimo

Abstract

Given an edge weighted undirected graph G and a positive integer d, the Min-degree Constrained Minimum Spanning Tree Problem (MDMST) consists of finding a minimum cost spanning tree T of G, such that each vertex is either a leaf or else has a degree at least d in T. The MDMST was recently proposed and belongs to the class NP-Hard for d >= 3. In this work, we discuss several formulations and optimization algorithms for the problem. We start by introducing two Integer Programming Formulations based on exponentially many undirected and directed subtour breaking constraints and compare the strength of their Linear Programming bounds, both theoretically and computationally. A Branch-and-cut (BC) algorithm and a Local Branching method that uses BC as its inner solver are proposed, both based on the strongest formulation, the directed one. Aiming to overcome the fact that the directed formulation is not symmetric with respect to the Linear Programming bounds, we also present a symmetric and compact reformulation, devised with the application of an intersection reformulation technique to the directed model. The reformulation proved to be much stronger than the previous models, but evaluating its bounds directly by Linear Programming solvers is very time consuming. Therefore, we propose a Lagrangian Relaxation algorithm for approximating them. Attempting to speed up the computation of the Lagrangian dual bounds, we implemented a parallel Subgradient Method. We also introduced a Lagrangian heuristic based on the Local Branching algorithm. With the proposed methods, several new optimality certificates, best lower and upper bounds for MDMST are provided.