期刊
ANNALS OF OPERATIONS RESEARCH
卷 298, 期 1-2, 页码 65-78出版社
SPRINGER
DOI: 10.1007/s10479-018-2895-y
关键词
Minimum spanning tree; Conflicting edges; Branch-and-cut
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据