期刊
MATHEMATICAL PROGRAMMING
卷 145, 期 1-2, 页码 349-376出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-013-0650-3
关键词
-
类别
资金
- National Science Foundation [CMMI-0800676, CMMI-1100765]
- Defense Threat Reduction Agency [HDTRA1-08-1-0029, HDTRA1-10-1-0050]
- US Department of Homeland Security [2008-DN-077-ARI021-05]
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [1100765] Funding Source: National Science Foundation
We consider a version of the stochastic network interdiction problem modeled by Morton et al. (IIE Trans 39:3-14, 2007) in which an interdictor attempts to minimize a potential smuggler's chance of evasion via discrete deployment of sensors on arcs in a bipartite network. The smuggler reacts to sensor deployments by solving a maximum-reliability path problem on the resulting network. In this paper, we develop the (minimal) convex hull representation for the polytope linking the interdictor's decision variables with the smuggler's for the case in which the smuggler's origin and destination are known and interdictions are cardinality-constrained. In the process, we propose an exponential class of easily-separable inequalities that generalize all of those developed so far for the bipartite version of this problem. We show how these cuts may be employed in a cutting-plane fashion when solving the more difficult problem in which the smuggler's origin and destination are stochastic, and argue that some instances of the stochastic model have facets corresponding to the solution of NP-hard problems. Our computational results show that the cutting planes developed in this paper may strengthen the linear programming relaxation of the stochastic model by as much as 25 %.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据