Premium
Minimizing a stochastic maximum‐reliability path
Author(s) -
Pan Feng,
Morton David P.
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20238
Subject(s) - interdiction , path (computing) , mathematical optimization , reliability (semiconductor) , constraint (computer aided design) , computer science , relaxation (psychology) , integer programming , decomposition , linear programming , mathematics , engineering , psychology , social psychology , power (physics) , ecology , physics , geometry , quantum mechanics , biology , programming language , aerospace engineering
Abstract 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. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008