Algoritmos branch-and-cut-and-price para o problema da árvore geradora de custo mínimo com restrição de grau

• Ano de defesa: 2014
• Autor(a) principal: Luis Henrique Costa Bicalho
• 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: Otimização combinatória; Geração de colunas; Branch-and-cut-and-price; Branch-and-cut; AGM com restrição de grau; Análise Numérica; Árvores (Teoria dos Grafos); Computação
• Link de acesso: http://hdl.handle.net/1843/ESBF-9Q3N8R

Given an undirected graph G = (V, E) with weighted edges and positive integers dv associated with each vertex v ∈ V , the Degree-Constrained Minimum Spanning Tree Problem (DCMST) consists in nding a minimum cost spanning tree T of G such that the degree of each vertex v in T is less than or equal to dv . In this work, we propose a hybrid algorithm that uses Column Generation as preprocessor and warm start to a Branch-and-cut algorithm and a Branch-and-cut-and-price algorithm for the DCMST. These approaches were tested in benchmarks available in the literature and in a new, more dicult, set of instances introduced in this work. In small and medium sized instances, the approaches proposed are better than those of the literature, obtaining optimality certicates spending less processing time. For the largest instances, the proposed methods require more CPU time due to the fact that the subtour elimination constraints separating algorithm is costly.