Stochastic network interdiction 101

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 p=0.5 and is only able to interdict two arcs.

simple_network

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 (s,a) and (s,t). It doesn’t make sense to interdict (a,t), because we are already interdicting (s,a) (we are approaching this is a deterministic maximum-flow problem!). This leaves the adversary with a maximum flow of (1 - 0.5)(100) + (1 - 0.5)(10) = 55.

simple_network_sa_st

However, the real solution in this problem is to interdict arcs (s,a) and (a,t).

simple_network_sa_at

Consider the four scenarios.

snip_table

When these arcs are interdicted, the expected maximum flow through the network becomes (0.25)(10) + (0.25)(10) + (0.25)(10) + (0.25)(110) = 35.

I’ll conclude by presenting the basic formulation for the stochastic network interdiction problem. We’ll be using mostly all-too-familiar notation.

  • G=(N,A): the directed network
  • A' = A \cup \{ (t,s) \}
  • u_{ij}: capacity of arc (i,j)\in A'
  • R: interdiction budget
  • r_{ij}: cost of interdicting arc (i,j)\in A'
  • p_{ij}: probability of successful interdiction on arc (i,j)\in A'
  • s\in N: the adversary’s origin
  • t\in N: the adversary’s destination
  • \tilde{I}_{ij}: indicator random variable for each arc that is 1 with probability p_{ij} and 0 with probability 1-p_{ij}
  • x_{ij}: flow through arc (i,j)\in A'
  • \gamma_{ij}: whether the leader interdicts arc (i,j)\in A'

We’ll include variable x_{ts} as our dummy “max-flow arc” like we do in a standard maximum-flow formulation. We let u_{ts}=\sum_{(i,j)\in A} u_{ij} + 1 and r_{ts}=R+1. That is, let (t,s) 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 \tilde{I} 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 (i,j) is successful at reducing the arc capacity to zero with probability p_{ij}. Otherwise, the interdiction has no effect.

w^* = \min \mathbb{E}[h(\gamma,\tilde{I})] \\  \phantom{XXX}\text{s.t.} \displaystyle\sum_{(i,j)\in A} r_{ij}\gamma_{ij} \leq R \\  \phantom{XXXs.t.} \gamma_{ij}\in\{0,1\} \phantom{XXX} \forall (i,j)\in A'

where:

h(\gamma,\tilde{I}) = \max x_{ts} \\  \phantom{XXXXX}\text{s.t.} \displaystyle\sum_{j : (i,j)\in A} x_{ij} + \displaystyle\sum_{j : (j,i)\in A} x_{ji} = 0 \phantom{XXX} \forall i\in N \\  \phantom{XXXXXs.t.}0\leq x_{ij} \leq u_{ij}(1 - \tilde{I}_{ij}\gamma_{ij}) \phantom{XXXXx} \forall (i,j)\in A'

The first constraint family in the above definition of h(\gamma,\tilde{I}) is our typical flow-balance constraints. The second constraint effectively reduces the capacity of arc (i,j)\in A' to zero if the arc is interdicted and the realization of \tilde{I}_{ij} is 1.

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.

Advertisements

3 thoughts on “Stochastic network interdiction 101

  1. Thanks for covering this Eli. I appreciate your explanation of the fallacy of deterministically using expected values. I will be curious on Thursday to hear your thoughts on the best way to implement this in practice with the different possible realizations

    I am curious if some models allow for interdicting arcs at different levels. That is rather than just a single shot of interdicting the arc with a 50% chance of success, you could choose to devote more resources to interdicting the arc and get a higher chance of success or less resources and a lower chance of success.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s