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

Abstract

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.