Protecting Critical Assets: The r-interdiction Median Problem with Fortification

Many systems contain bottlenecks, critical linkages, and key facilities. Such components, when lost due to a man-made or natural disaster, may imperil a system in performing its intended function. This article focuses on reducing the impact of an intentional strike against a supply system where supply facilities can be fortified in order to prevent such events. It is assumed that fortification resources are limited and must be used in the most efficient manner. In a recent article, Church, Scaparra, and Middleton (2004) introduced the r-interdiction median problem, which can be used to identify the most important facilities in a supply system. In this article, we extend that model to address the option of fortifying such sites against possible interdiction. We present a new integer-linear programming model that optimally allocates fortification resources in order to minimize the impact of interdiction. Computational results are presented in using this model for several hypothetical problems. We also discuss the general properties of fortification and demonstrate that the presence of fortification can impact which system elements are considered critical.