dc.contributor | Sebastián Alberto Urrutia | |
dc.contributor | Abilio Pereira da Lucena Filho | |
dc.contributor | Geraldo Robson Mateus | |
dc.contributor | Martin Gomez Ravetti | |
dc.contributor | Thiago Ferreira de Noronha | |
dc.creator | Phillippe Samer Lallo Dias | |
dc.date.accessioned | 2019-08-13T16:48:16Z | |
dc.date.accessioned | 2022-10-03T22:46:58Z | |
dc.date.available | 2019-08-13T16:48:16Z | |
dc.date.available | 2022-10-03T22:46:58Z | |
dc.date.created | 2019-08-13T16:48:16Z | |
dc.date.issued | 2014-02-14 | |
dc.identifier | http://hdl.handle.net/1843/ESBF-9KJQNW | |
dc.identifier.uri | http://repositorioslatinoamericanos.uchile.cl/handle/2250/3810461 | |
dc.description.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. | |
dc.publisher | Universidade Federal de Minas Gerais | |
dc.publisher | UFMG | |
dc.rights | Acesso Aberto | |
dc.subject | Restrições de conflito | |
dc.subject | Conjunto independente | |
dc.subject | Optimal trees | |
dc.subject | Integer programming formulations | |
dc.subject | Árvores ótimas | |
dc.subject | Branch and cut | |
dc.subject | Stable set | |
dc.subject | Conflict constraints | |
dc.subject | Formulações em programação inteira | |
dc.title | Formulations and exact algorithms for the minimumspanning tree problemwith conflicting edge pairs | |
dc.type | Dissertação de Mestrado | |