Stochastic network interdiction: models and methods

We develop stochastic network interdiction models and associated solution methods. In its simplest form, our model consists of a smuggler who wishes to traverse a network from an origin to a destination without being detected. Probabilities associated with the indigenous transportation network specify likelihoods that a smuggler can traverse each arc in the network undetected. By installing a detector on an arc we can decrease that probability. The decisionmaking problem is to select arcs to receive detectors subject to budget and policy constraints. The goal is to minimize the probability that a smuggler evades detection when the smuggler’s origin-destination pair is known only through a probability distribution. The model has two stages: first we install detectors then the random origin-destination pair of the smuggler is revealed and the smuggler selects a maximum-reliability path knowing detector locations and detection probabilities. When we consider that detectors can only be installed on the “boundary” of the network, we show that the model can be reduced to an interdiction problem on a simpler bipartite network. In other variants of the model, the smuggler has partial information on detector locations and may have a different perception (than the interdictor) of the detection probabilities. These models are cast as stochastic mixed-integer programs, and the complexity of the models is investigated. Our solution procedure includes scenario reduction, other preprocessing techniques and decomposition methods, all exploiting special structures in our stochastic network interdiction problems. We further enhance our solution procedures by developing a class of valid inequalities to tighten the integer-programming formulation. This work is motivated by the Second Line of Defense (SLD) program, a cooperative effort between the US Department of Energy and the Russian Federation State Customs Committee. SLD’s primary goal is to minimize the risk of illicit trafficking of nuclear materials and technologies through detection and deterrence by enhancing border detection capabilities.