Exact interdiction models and algorithms for disconnecting networks via node deletions

作     者：Shen, Siqian Smith, J. Cole Goli, Roshan 

作者机构：Univ Michigan Dept Ind & Operat Engn Ann Arbor MI 48109 USA Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Univ Florida Grad Sch Business Gainesville FL 32611 USA 

出 版 物：《DISCRETE OPTIMIZATION》 (离散优化)

年 卷 期：2012年第9卷第3期

页      面：172-188页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070102[理学-计算数学] 0701[理学-数学] 

基　　金：Defense Threat Reduction Agency [HDTRA1-10-1-0050] National Science Foundation [CMMI-1100765] Directorate For Engineering Div Of Civil, Mechanical, & Manufact Inn Funding Source: National Science Foundation 

主　　题：Network interdiction Mixed-integer programming Valid inequalities 

摘      要：This paper analyzes the problem of maximizing the disconnectivity of undirected graphs by deleting a subset of their nodes. We consider three metrics that measure the connectivity of a graph: the number of connected components (which we attempt to maximize), the largest component size (which we attempt to minimize), and the minimum cost required to reconnect the graph after the nodes are deleted (which we attempt to maximize). We formulate each problem as a mixed-integer program, and then study valid inequalities for the first two connectivity objectives by examining intermediate dynamic programming solutions to k-hole subgraphs. We randomly generate a set of test instances, on which we demonstrate the computational efficacy of our approaches. Published by Elsevier B.V.