Using limited assets, an interdictor attempts to destroy parts of a capacitated network through which an adversary will subsequently maximize flow. We formulate and solve a stochastic version of the interdictor's problem: Minimize the expected maximum flow through the network when interdiction successes are binary random variables. Extensions are made to handle uncertain arc capacities and other realistic variations. These two-stage stochastic integer programs have applications to interdicting illegal drugs and to reducing the effectiveness of a military force moving materiel, troops, information, etc., through a network in wartime. Two equivalent model formulations allow Jensen's inequality to be used to compute both lower and upper bounds on the objective, and these bounds are improved within a sequential approximation algorithm. Successful computational results are reported on networks with over 100 nodes, 80 interdictable arcs, and 180 total arcs. T his paper investigates stochastic variants of a network interdiction problem where an "interdictor," using limited assets, "interdicts" (destroys or at least stops the use of) parts of a capacitated network through which an adversary will subsequently maximize flow. The deterministic problem is to minimize the maximum achievable flow through the network subject to constraints on interdiction resources. In the stochastic variants, interdiction successes can be uncertain and/or arc capacities can be random variables. The objective of these stochastic network interdiction problems is to minimize the expected maximum flow through the network by selecting the best set of arcs to interdict, or to attempt to interdict. The deterministic network interdiction problem has been studied in McMasters and Mustin (1970 ), Steinrauf (1991 ), Phillips (1992 ), and Wood (1993 , with military applications and with applications to the interdiction of illegal drugs and precursor chemicals. Game-theoretic network interdiction models have also been studied (Wollmer 1964, Washburn and Wood 1995) , but these models are substantially different: they determine optimal arcinspection strategies for detecting an evader moving through a network surreptitiously. Our analysis of stochastic network interdiction begins with this basic problem: We wish to interdict arcs in a network so as to minimize the expected maximum flow from a source node s to a sink node t. Assets available to perform these interdictions are limited. Interdiction successes are assumed to be independent binary random variables such that an unsuccessful interdiction attempt on an arc leaves the arc with its nominal capacity, and a successful interdiction leaves the arc with no capacity. A stochastic maximum flow problem cannot be solved by solving a deterministic maximum flow problem where random arc capacities are replaced by their expected values. Likewise, our interdiction problem cannot be solved via the deterministic "expected-value problem" (Birge 1982) that minimizes maximum flow assuming uninterdicted arcs have nominal capacities and interdicted arcs have their expected residual (after-interdiction) capacities. Consider the simple interdiction problem represented in Figure 1 , where each arc is marked with its nominal capacity. Assume that the probability of a successful interdiction on any arc is 0.6, at most one interdiction on each arc may be attempted, and resources limit the number of interdictions to two. The expected-value problem selects arcs (s, t) and (s, 2), or arcs (s, t) and (2, t) for interdiction. The capacity of the network based on expected capacities following interdiction is (1 Ϫ 0.6)10 ϩ (1 Ϫ 0.6)100 ϭ 44. This capacity would be (1)10 ϩ (1 Ϫ 0.6)100 ϭ 50 if arcs (s, 2) and (2, t) were interdicted, since nothing is gained in a deterministic model by interdicting identical arcs in series. The
As for the literature in stochastic network interdiction problem, authors in REF provide a thorough introduction to many variations of stochastic network interdiction.
Stochastic Network Interdiction
Oper. Res.
Oper. Res.
Computer Science Mathematics