Robust Network Interdiction Considering Multiple Defense Resources

Abstract

We extend the network interdiction problem in order to consider multiple options for defending arcs in a network. We apply our model to select an optimal set of countermeasures for nuclear material smuggling. In order account for the joint impact of multiple countermeasures, we consider multiple components of defense: situational awareness, detection, and interdiction. We develop a bi-level programming model, where the adversary's goal is to maximize damage to the system while the defender seeks to minimize damage by selecting countermeasure options under a restricted bud- get. Furthermore, since effectiveness of countermeasures is often difficult to assess with high accuracy, we use robust optimization to allow for parametric uncertainty. We test our method on a synthetic example of the U.S. supply chain network that includes rail, air, and maritime transportation between both domestic and international locations. For this test example, we find that increasing the budget for countermeasures has the greatest impact within the first 1-2% of the cost to implement all countermeasures and that the uncertainty tolerance has a greater impact on expected damage than the countermeasure budget does. Thus, when strategically selecting countermeasures it is important to precisely understand the effectiveness of each option and the adversary's probability of subverting them.