Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach

被引：0
作者：
Francesco Carrabs
Raffaele Cerulli
Rosa Pentangelo
Andrea Raiconi
机构：
[1] University of Salerno,Department of Mathematics
来源：
Annals of Operations Research | 2021年 / 298卷
关键词：
Minimum spanning tree; Conflicting edges; Branch-and-cut;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：65 / 78
页数：13
相关论文
共 50 条
[11]   Branch-and-cut-and-price algorithms for the Degree Constrained Minimum Spanning Tree Problem [J].
Bicalho, Luis Henrique ;
da Cunha, Alexandre Salles ;
Lucena, Abilio .
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2016, 63 (03) :755-792
[12]   A robust branch-and-cut approach for the minimum-energy symmetric network connectivity problem [J].
Li, Xiangyong ;
Aneja, Y. P. ;
Huo, Jiazhen .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2012, 40 (02) :210-217
[13]   A branch-and-cut approach to the crossing number problem [J].
Buchheim, Christoph ;
Chimani, Markus ;
Ebner, Dietmar ;
Gutwenger, Carsten ;
Juenger, Michael ;
Klau, Gunnar W. ;
Mutzel, Petra ;
Weiskircher, Rene .
DISCRETE OPTIMIZATION, 2008, 5 (02) :373-388
[14]   Branch-and-Cut Algorithms for Steiner Tree Problems with Privacy Conflicts [J].
Hill, Alessandro ;
Voss, Stefan ;
Baldacci, Roberto .
COMPUTING AND COMBINATORICS, COCOON 2019, 2019, 11653 :266-278
[15]   A note on the article "A robust branch-and-cut approach for the minimum-energy symmetric network connectivity problem" [J].
Montemanni, R. ;
Gambardella, L. M. .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2012, 40 (06) :817-817
[16]   A Branch-and-Cut Algorithm for the k-Edge Connected Subgraph Problem [J].
Bendali, F. ;
Diarrassouba, I. ;
Mahjoub, A. R. ;
Biha, M. Didi ;
Mailfert, J. .
NETWORKS, 2010, 55 (01) :13-32
[17]   An efficient branch-and-cut algorithm for the minimum covering location problem with distance constraints [J].
Wang, Bo-Rui ;
Chen, Wei-Kun ;
Zhang, Yu-Hai ;
Yuan, Jian-Hua ;
Dai, Yu-Hong .
JOURNAL OF GLOBAL OPTIMIZATION, 2025,
[18]   A new branch-and-cut approach for the generalized regenerator location problem [J].
Li, Xiangyong ;
Aneja, Y. P. .
ANNALS OF OPERATIONS RESEARCH, 2020, 295 (01) :229-255
[19]   A branch-and-cut approach for the vehicle routing problem with loading constraints [J].
Hokama, Pedro ;
Miyazawa, Flavio K. ;
Xavier, Eduardo C. .
EXPERT SYSTEMS WITH APPLICATIONS, 2016, 47 :1-13
[20]   A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants [J].
Jozefowiez, Nicolas ;
Laporte, Gilbert ;
Semet, Frederic .
COMPUTERS & OPERATIONS RESEARCH, 2011, 38 (11) :1534-1542
12345