Network interdiction models are used to model a how a “defender” should best react to the presence of an “attacker” on a network. In contrast to other network interdiction models, shortest-path network interdiction considers an attacker who is attempting to maximize their probability of reaching a given sink node from a given source node. The attacker has a probability of traversing each arc safely. The defender is able to “interdict” a subset of these arcs (within the confines of a budget) by placing sensors on them, thereby reducing the attacker’s probability of safely traversing that arc.
This network interdiction model can be seen as a bilevel game. As the defender, we attempt to minimize the attacker’s maximum-reliability path through the network. Many of the models are obtained by beginning with this min-max formulation and consolidating it into something more workable.
Here’s a picture to visualize what is happening. As defenders, we choose first the arcs on which to place sensors. Afterwards, the attacker will note our decision and take the “best” (maximum-reliability) path through the network.
On the picture, the red dashes represent sensors. The blue path represents the attacker’s maximum-reliability path through the network.
Let’s build a model! We’ll need to define a few things first.
- : our directed network
- : arcs on which we can place sensor
- : interdiction budget
- : cost of placing a sensor on arc
- : probability of attacker traversing arc undetected
- : probability of attacker traversing arc undetected when a sensor is present
- : value of maximum-reliability path from to with no sensors installed
- : the attacker’s starting point
- : the attacker’s goal
For our data to make sense, we must have .
Great! We’ll now add a few variables.
- : probability of attacker making it from node to node undetected
- : whether or not we place a sensor on arc
If is defined as above, we surely want . It only makes sense that if the attacker is present at the ending goal, they will make it to their goal with probability .
Furthermore, we want $\pi_i$ to take on specific values based on our values of . Specifically, if we do interdict arc , we want to enforce . If we do not interdict arc , we want to enforce . Our objective will be to minimize . This will ensure that is calculated to the attacker’s best path from to .
Now let’s examine the model.
Remember when we wanted to enforce certain conditions on depending on our choices of for ? Let’s see if those hold!
Let . By the second constraint, we have , as desired. We also want to ensure the third constraint is dominated by this constraint; that is, it has no bearing on the model. Because we have . This proves the third constraint is dominated by the second.
Now, let . By the third constraint, we have , which is again what we want. We will also ensure the second constraint is dominated by this constraint. Because and , we have . Thus, the second constraint is indeed dominated by the third.
In a few weeks, we’ll be taking a closer look at the stochastic case of the maximum-reliability network problem, in which the attacker’s starting and ending points are unknown.
Anyways, back to watching The Bachelor finale. I’m totally only watching because my wife is. #TeamLauren
Cormican, Kelly J., David P. Morton, and R. Kevin Wood. “Stochastic network interdiction.” Operations Research 46.2 (1998): 184-197.