In this post, I would like to write about the second paper I will present in class. I chose a paper about multicommodity flow network interdiction, since both multicommodity flow and network interdiction models are interesting topics to me.
As Amanda and Eli mentioned in their previous blog posts, network interdiction models have lots of applications especially for the military and homeland security.
In network interdiction models, we have a leader who destroys arcs to disrupt the follower’s (enemy) flows. In the paper, “Algorithms for Discrete and Continuous Multicommodity Flow Network Interdiction Problems,” the model allows for more than one supply node for each commodity and multiple demand nodes. As an objective the leader interdicts the arcs to minimize the follower’s optimal reward with the budget B. The paper considers the discrete and continuous cases for interdiction. While in the discrete case each arc can be fully destroyed or operational, in the continuous case each arc can be partially destroyed so then depending on the percentage of disruption the capacity of arc changes.
The mathematical model is as follows:
where y is follower’s decision variable and x is the leader’s decision variable. Hence x is the percentage ofarc disruption and y is the amount of flow passing through that arc. Writers present several methods to solve both the discrete and continuous interdiction models. Here I would like to focus more on one specific application area of the interdiction models….like a Zombie attack!!!
To reach a safe place from Zombie attack, we can use shortest path models and with interdiction model, we can also slow down the attack. In this context, we can consider the enemy as zombies, the leader as human, and adapt the problem to disruption of zombie attack problem, which is one of the most IMPORTANT!!! homeland security issues. Now, the objective becomes to minimize the zombie attack achievement since they want to eat human’s brains and we want to escape from them. There are some guidelines out there on how to escape from Zombie attack, but as operations researcher, we should use our tools to achieve it. We can suppose that after having the first bit of brain they would like to eat more and more… But I’m not sure – just guessing. Anyway with this network interdiction idea, we can decrease the number of our friends that get slaughtered and recruited… Here we can see how interdiction models are helping us to secure our homeland not just from bad people but also from the zombies.
If you wonder more about Zombies, there is a whole archive at the “Punk Rock Operation Research” blog (https://punkrockor.com/tag/zombies/) and even a zombie apocalypse course in the University of Michigan to teach students survival skills.
Note: Stochastic network interdiction is also studied in the literature and there is a great source for that by Janjarassuk and Linderoth..
References:
Lim, Churlzu, and J. Cole Smith. “Algorithms for discrete and continuous multicommodity flow network interdiction problems.” IIE Transactions 39.1 (2007): 15-26.
Janjarassuk, U. and Linderoth, J. (2008), Reformulation and sampling to solve a stochastic network interdiction problem. Networks, 52: 120–132. doi:10.1002/net.20237
Public Sector Operations Research 
Thanks for writing about zombies! I’ve been waiting all semester for someone to do this 🙂
LikeLike
This student most assuredly deserves an ‘A’ for citing such relevant and seminal literature.
(Unlike that Eli kid who responds with snarky comments when Big Shot professors like me take their precious time to offer constructive criticism).
LikeLiked by 1 person