My upcoming presentation covers stochastic network interdiction. This is an extension of the deterministic network interdiction problem covered in class (highlighted in Wood, 1993).
In typical Stackelberg fashion, stochastic network interdiction pits an interdicter (leader) against an adversary (follower) on a capacitated network. As is the case in the deterministic case, the interdictor chooses which arcs to interdict, thereby reducing the arc’s capacity to zero. Afterwards, the adversary attempts to maximize the flow of a commodity from a predetermined source node to a predetermined sink node. The interdictor’s goal is to minimize the adversary’s maximum flow through the network. Unlike the deterministic case, the interdictor will only successfully interdict an arc with a certain probability.
It does seem enticing to model this as a deterministic network interdiction problem, where the interdictor always successfully interdicts the arcs, and we replace the arcs’ “interdicted” capacities with their expected values. Although enticing, this approach will not work. Consider the simple network below. The interdictor successfully interdicts any arc with probability and is only able to interdict two arcs.
Let’s attempt to convert this to a deterministic problem. We do this by assuming the interdictor will always be successful in his or her attempts to interdict an arc. Furthermore, we replace the interdicted arc capacities with their expected values. In this case, the optimal interdiction plan is to interdict arcs and . It doesn’t make sense to interdict , because we are already interdicting (we are approaching this is a deterministic maximum-flow problem!). This leaves the adversary with a maximum flow of .
However, the real solution in this problem is to interdict arcs and .
Consider the four scenarios.
When these arcs are interdicted, the expected maximum flow through the network becomes .
I’ll conclude by presenting the basic formulation for the stochastic network interdiction problem. We’ll be using mostly all-too-familiar notation.
- : the directed network
- : capacity of arc
- : interdiction budget
- : cost of interdicting arc
- : probability of successful interdiction on arc
- : the adversary’s origin
- : the adversary’s destination
- : indicator random variable for each arc that is with probability and with probability
- : flow through arc
- : whether the leader interdicts arc
We’ll include variable as our dummy “max-flow arc” like we do in a standard maximum-flow formulation. We let and . That is, let be treated as a normal arc that will never achieve its upper bound and will never be interdicted.
The model looks very similar to a standard maximum flow problem, though we account for the different realizations of by throwing an expected value in the objective function. Additionally, we account for interdiction by modifying the upper bound constraints for the flow variables. Remember: an interdiction on arc is successful at reducing the arc capacity to zero with probability . Otherwise, the interdiction has no effect.
The first constraint family in the above definition of is our typical flow-balance constraints. The second constraint effectively reduces the capacity of arc to zero if the arc is interdicted and the realization of is .
In the presentation, we’ll discuss the authors’ clever approach to solving this nightmarish problem.
Source: Cormican, Kelly J., David P. Morton, and R. Kevin Wood. “Stochastic network interdiction.” Operations Research 46.2 (1998): 184-197.