Algoritmos branch-and-cut-and-price para o problema da árvore geradora de custo mínimo com restrição de grau
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Abilio Pereira da Lucena Filho
Geraldo Robson Mateus
Geraldo Robson Mateus
Resumo
Dados um grafo não direcionado G = (V, E) com pesos nas arestas e inteiros positivos dv associados a cada vértice v ∈ V , o Problema da Árvore Geradora de Custo Mínimo com Restrição de Grau (PAGRG) consiste em encontrar uma árvore geradora mínima T de G tal que o grau de cada vértice v em T seja menor ou igual a dv. Neste trabalho, foram propostos um algoritmo híbrido que utiliza Geração de Colunas como etapa de preprocessamento e warm start de um algoritmo Branch-and-cut e um algoritmo Branch-and-cut-and-price para o PAGRG. Essas abordagens foram testadas em instâncias da literatura e em um novo conjunto de instâncias, mais difíceis, introduzidas neste trabalho. Em instâncias de pequeno e médio porte as abordagens utilizadas foram melhores do que as da literatura, obtendo certicados de otimalidade em um menor tempo de processamento. Já para as instâncias maiores, devido ao alto custocomputacional do algoritmo de separação das restriçoes de eliminação de subciclos, os métodos propostos foram mais lentos.
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.
Assunto
Análise Numérica, Otimização combinatória, Árvores (Teoria dos Grafos), Computação
Palavras-chave
Otimização combinatória, Geração de colunas, Branch-and-cut-and-price, Branch-and-cut, AGM com restrição de grau