DETERMINISTIC NETWORK INTERDICTION

Interest in network interdiction has been rekindled because of attempts to reduce the flow of drugs and precursor chemicals moving through river and road networks in South America. This paper considers a problem in which an enemy attempts to maximize flow through a capacitated network while an interdictor tries to minimize this maximum flow by interdicting (stopping flow on) network arcs using limited resources. This problem is shown to be NP-complete even when the interdiction of an arc requires exactly one unit of resource. New flexible, integer programming models are developed for the problem and its variations and valid inequalities and a reformulation are derived to tighten the LP relaxations of some of these models. A small computational example from the literature illustrates a hybrid (partly directed and partly undirected) model and the usefulness of the valid inequalities and the reformulation.