Journal
ANNALS OF OPERATIONS RESEARCH
Volume 298, Issue 1-2, Pages 65-78Publisher
SPRINGER
DOI: 10.1007/s10479-018-2895-y
Keywords
Minimum spanning tree; Conflicting edges; Branch-and-cut
Categories
Ask authors/readers for more resources
The paper presents a branch-and-cut approach to solve the minimum spanning tree problem with conflicting edge pairs, demonstrating its superiority over previous algorithms through computational tests on benchmark instances and newly proposed ones.
In this paper, we show a branch-and-cut approach to solve the minimum spanning tree problem with conflicting edge pairs. This is a NP-hard variant of the classical minimum spanning tree problem, in which there are mutually exclusive edges. We introduce a new set of valid inequalities for the problem, based on the properties of its feasible solutions, and we develop a branch-and-cut algorithm based on them. Computational tests are performed both on benchmark instances coming from the literature and on some newly proposed ones. Results show that our approach outperforms a previous branch-and-cut algorithm proposed for the same problem.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available