Optimization Online


A branch and cut algorithm for minimum spanning trees under conflict constraints

Phillippe Samer (samer***at***dcc.ufmg.br)
Sebastián Urrutia (surrutia***at***dcc.ufmg.br)

Abstract: We study approaches for the exact solution of the \NP--hard minimum spanning tree problem under conflict constraints. Given a graph $G(V,E)$ and a set $C \subset E \times E$ of conflicting edge pairs, the problem consists of finding a conflict-free minimum spanning tree, i.e. feasible solutions are allowed to include at most one of the edges from each pair in $C$. The problem was introduced recently in the literature, with several results on its complexity and approximability. Some formulations and both exact and heuristic algorithms were also discussed, but computational results indicate considerably large duality gaps and a lack of optimality certificates for benchmark instances. In this paper, we build on the representation of conflict constraints using an auxiliary conflict graph $\hat{G}(E,C)$, where stable sets correspond to conflict-free subsets of $E$. We introduce a general preprocessing method and a branch and cut algorithm using an IP formulation with exponentially sized classes of valid inequalities for both the spanning tree and the stable set polytopes. Encouraging computational results indicate that the dual bounds of our approach are significantly stronger than those previously available, already in the initial LP relaxation, and we are able to provide new feasibility and optimality certificates.

Keywords: Optimal trees, Conflict constraints, Stable set, Branch and cut

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Integer Programming (0-1 Programming )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Phillippe Samer, Sebastián Urrutia (2014), "A branch and cut algorithm for minimum spanning trees under conflict constraints". Accepted for publication on Optimization Letters: 10.1007/s11590-014-0750-x

Download: [PDF]

Entry Submitted: 07/04/2013
Entry Accepted: 07/05/2013
Entry Last Modified: 06/30/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society