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

• Ano de defesa: 2012
• Autor(a) principal: Leonardo Conegundes Martinez
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; UFMG
• Palavras-chave em Português: relaxação lagrangeana; mínimo com restrição de grau mínimo; branch-and-cut; local branching; otimização combinatória; programação paralela; formulações de programação inteira; problema da árvore geradora de custo; Computação
• Link de acesso: http://hdl.handle.net/1843/ESBF-8SULUR

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.