Deterministic Network Interdiction
MetadataShow full item record
Interest in network interdiction has been rekindled because of attempts to reduce the flow of drugs and precursor chemicals 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 relaxation 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.
Mathematical and Computer Modelling, 17, pp. 1‐18.Center for Infrastructure Defense (CID) Paper.
RightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Showing items related by title, author, creator and subject.
Agrawal, B.N. (1993);This paper presents a boundary-layer model to predict dynamic characteristics of liquid motion in partially filled tanks of a spinning spacecraft. The solution is obtained by solving three boundary-value problems: an ...
Schwartz, Garry S. (Monterey, California. Naval Postgraduate School, 1993-03);This thesis addresses two problems in aligning the recruiting structure for Navy Recruiting Command. The first problem involves two decisions affecting recruiting stations within a single recruiting district: which stations ...
On partitioning an arbitrarily given set of elements of a finite Boolean algebra into the minimum number of sets of compatible elements Colwell, Samuel C., III (Monterey, California. Naval Postgraduate School, 1964);During the past several years at the United States Naval Postgraduate School there has been much interest in obtaining an efficient method for making a time schedule for classes. A mathematical model for a simplified ...