Use este identificador para citar o ir al link de este elemento:
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 |
primer Tutor: | Sebastián Alberto Urrutia |
primer miembro del tribunal : | Abilio Pereira da Lucena Filho |
Segundo miembro del tribunal: | Geraldo Robson Mateus |
Tercer miembro del tribunal: | Martin Gomez Ravetti |
Cuarto miembro del tribunal: | Thiago Ferreira de Noronha |
Resumen: | 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. |
Asunto: | Programação inteira Otimização combinatória Computação |
Idioma: | Inglês |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Institución: | UFMG |
Tipo de acceso: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/ESBF-9KJQNW |
Fecha del documento: | 14-feb-2014 |
Aparece en las colecciones: | Dissertações de Mestrado |
archivos asociados a este elemento:
archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
phillippesamer.pdf | 1.17 MB | Adobe PDF | Visualizar/Abrir |
Los elementos en el repositorio están protegidos por copyright, con todos los derechos reservados, salvo cuando es indicado lo contrario.