Minimizing a stochastic maximum-reliability path

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 (2007)), 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.