.png){kind=icon}
返回
Efficient Benders decomposition for distance-based critical node detection problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.omega.2019.02.006.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This paper addresses the critical node detection problem which seeks a subset of nodes for removal in order to maximize the disconnectivity of the residual graph with respect to a specific distance-based measure, namely the Wiener index. Such a measure is defined based on the all-pair shortest path distances in the residual graph so that the longer the total length of shortest paths, the greater the value of the disconnectivity measure. In the literature, a mixed integer linear programming model and an exact iterative-based method have been presented for this problem; however, both approaches become very time-consuming on graphs having large diameter and non-unit edge lengths. To overcome this shortcoming, in this paper, we present a new formulation for the problem and solve it by Benders decomposition algorithm. We improve the performance of Benders algorithm by several techniques (including analytical calculation of dual variables, generation of good-quality initial optimality cuts, considering master's optimality cuts as lazy constraints, etc.) to reduce the total running time. The extensive computational experiments on instances, taken from the literature or generated randomly, confirm the effectiveness of the new approaches. (C) 2019 Elsevier Ltd. All rights reserved.
Keyword:
Critical node detection
Wiener measure
Benders decomposition
Analytical resolution of sub-problem
Solution pool
Lazy constraint
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
O
IF:
7.2
论文数:
3.7K
被引数:
1.4W
机构
引用论文
分享收藏Benders decomposition for a strategic network design problem under NAFTA local content requirements
PREAI
分享收藏Identification of Vital Nodes in Complex Network via Belief Propagation and Node Reinsertion.png)
IEEE ACCESS
OAAI
IEEE ACCESSIF3.6
OAAI分享收藏First Report of Zoonotic Genotype of Giardia duodenalis in Mussels (Mytilus edulis) from Patagonia Argentina来自阿根廷巴塔哥尼亚的贻贝 (Mytilus edulis) 中 十二指肠贾第鞭毛虫 的人畜共患病基因型的第一份报告
OAAI
OAAI分享收藏
查看更多内容