O problema do subgrafo biconexo mínimo generalizado: algoritmos e formulações
Carregando...
Arquivos
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
Carlos Roberto V de Carvalho
Luidi Simonetti
Luidi Simonetti
Resumo
Dados um número inteiro k > 2 e um grafo simples não-direcionado G = (V; E ) com pesos reais positivos nas arestas, onde V está particionado em k subconjuntos (ou clusters ), o Problema do Subgrafo Biconexo Mínimo Generalizado (PSBMG) equivale a encontrar um subgrafo biconexo de custo mínimo S de G que contenha exatamenteum vértice de cada cluster de G. Neste trabalho, foram propostos um algoritmo exato Branch-and-cut e heurísticas para solucionar o PSBMG. O algoritmo Branch-and-cut separa quatro classes de desigualdades válidas para o problema em questão, todas elas generalizadas de outros problemas da literatura relacionados ao PSBMG. Para avaliar as abordagens de solução introduzidas, foram realizados testes computacionais em instâncias de benchmark densas e esparsas. Para um número considerável delas, foi possível prover novos certicados de otimalidade e mehores limites inferiores e superi-ores.
Abstract
Given an integer number k > 2 and an undirected simple graph G = (V; E) with positive real weights assigned to its edges, where V is partitioned into k subsets (or clusters), the Generalized Minimum Biconnected Subgraph Problem (GMBSP) amounts to nding a minimum-cost biconnected subgraph S of G, such that S contains exactly one vertex from every cluster of G. In this work, we propose an exact Branch-and-cut algorithm and some heuristics to solve PSBMG. Our Branch-and-cut algorithm separates four classes of valid inequalities for GMBSP, all of them adapted from valid inequalities for other problems related to GMBSP. In order to better assess our solution approaches, we conducted several computational experiments using dense and sparse benchmark instances. For a considerable fraction of those instances, we were able to provide new optimality certicates, as well as better upper and lower bounds.
Assunto
Computação
Palavras-chave
Algoritmos branch-and-cut, Projeto de redes resilientes, Biconexidade em teoria de grafos