期刊
NETWORKS
卷 52, 期 3, 页码 111-119出版社
WILEY
DOI: 10.1002/net.20238
关键词
network interdiction; stochastic programming; valid inequality
资金
- National Science Foundation [DMI-0217927, DMI-0228419, CBET-0736231]
We consider a stochastic network interdiction problem in which the goal is to detect an evader, who selects a maximum-reliability path. Subject to a resource constraint, the interdictor installs sensors on a subset of the network's arcs to minimize the value of the evader's maximum-reliability path, i.e., to maximize the detection probability. When this decision is made, the evader's origin-destination pair is known to the interdictor only through a probability distribution. Our model is framed as a stochastic mixed-integer program and solved by an enhanced L-shaped decomposition method. Our primary enhancement is via a valid inequality, which we call a step inequality. In earlier work [Morton et al., IIE Trans 39 (2007), 3-14], we developed step inequalities for the special case in which the evader encounters at most one sensor on an origin-destination path. Here, we generalize the step inequality to the case where the evader encounters multiple sensors. In this more general setting, the step inequality is tightly coupled to the decomposition scheme. An efficient separation algorithm identifies violated step inequalities and strengthens the linear programming relaxation of the L-shaped method's master program. We apply this solution procedure with further computational enhancements to a collection of test problems. (C) 2008 Wiley Periodicals, Inc.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据