Formulations and exact algorithms for the minimumspanning tree problemwith conflicting edge pairs

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.