Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/ESBF-9KJQNW
Tipo: | Dissertação de Mestrado |
Título: | Formulations and exact algorithms for the minimumspanning tree problemwith conflicting edge pairs |
Autor(es): | Phillippe Samer Lallo Dias |
Primeiro Orientador: | Sebastián Alberto Urrutia |
Primeiro membro da banca : | Abilio Pereira da Lucena Filho |
Segundo membro da banca: | Geraldo Robson Mateus |
Terceiro membro da banca: | Martin Gomez Ravetti |
Quarto membro da banca: | Thiago Ferreira de Noronha |
Resumo: | Este trabalho apresenta abordagens para a solução exata do problema de árvores geradoras míniimas sob restrições de conflito. Dados um grafo G(V,E) e um conjunto C E x E de pares de arestas conflitantes, busca-se uma árvore geradora mínima de G incluindo no máximo uma das arestas de cada par em C. O problema é NP-difícil no caso geral e, embora formulações e algoritmos tenham sido discutidos recentemente na literatura, resultados computacionais apresentavam gaps de dualidade consideravelmente grandes e não forneciam certificados de otimalidade para conjuntos de instâncias padrão do problema. Neste trabalho exploramos representações poliédricas de subconjuntos de arestas livres de conflitos como conjuntos independentes em um grafo de conflitos auxiliar (E,C). Apresentamos formulações em programação linear inteira envolvendo quatro classes de desigualdades com número exponencial de restrições: duas para representações poliédricas clássicas de árvores geradoras em G, duas fortalecendo a interseção com relaxações do politopo de conjuntos independentes em (restringindo cliques e ciclos ímpares). Propomos e avaliamos computacionalmente um método de pré-processamento e algoritmos branch and cut. As soluções obtidas superam de forma consistente os melhores resultados disponíveis na literatura anteriormente. Novos certificados de viabilidade e otimalidade são obtidos, além de limites duais mais fortes já na relaxação linear inicial das formulações, mesmo para instâncias mais difícies do benchmark padrão. |
Abstract: | This work presents approaches for the exact solution of the minimum spanning tree problem under conflict constraints. Given a graph G(V,E) and a set C E x E of conflicting edge pairs, the problem consists of finding a conflict-free minimum spanning tree, i.e. feasible solutions may include at most one of the edges from each pair in C. The problem is NP-hard in the general case. Although formulations and algorithms have been discussed recently in the literature, computational results indicate considerably large duality gaps and a lack of optimality certificates for the benchmark instances. In this work, we cnsider polyhedral representations of conflict-free edge subsets as stable sets i an auxiliary conflict graph (E,C). We present integer linear programming formulations including four classes of exponentially-many constraints: two of which correspond to classic polyhedral representations of spanning trees in G, and two for strengthening the intersection with relaxations of the polytope of stable sets in (with clique and odd-cycle inequalities). We introduce and evaluate a preprocessing method and branch and cut algorithms. Encouraging results consistently improve on those previously available in the literature. New feasibility and optimality certificates are provided, and stronger dual bounds are already obtained in the initial linear relaxation of the formulations, even for the hardest instances in the standard benchmark. |
Assunto: | Programação inteira Otimização combinatória Computação |
Idioma: | Inglês |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Instituição: | UFMG |
Tipo de Acesso: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/ESBF-9KJQNW |
Data do documento: | 14-Fev-2014 |
Aparece nas coleções: | Dissertações de Mestrado |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
phillippesamer.pdf | 1.17 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.