The shortest path interdiction problem with randomized interdiction strategies: complexity and algorithms

Shortest-path interdiction problems involve a leader and a follower playing a zero-sum game over a directed network. The leader interdicts a set of arcs, and arc costs increase as a function of the number of times they are interdicted. The follower observes the leader’s actions and selects a shortest path in response. The leader’s optimal interdiction strategy maximizes the follower’s minimum-cost path. In classic formulations of these problems, the leader’s interdiction actions are deterministic. In this paper the leader selects a policy of randomized interdiction actions, and the follower only knows the probability of where interdictions are deployed on the network. The follower identifies a path having the minimum expected cost, whereas the leader seeks to maximize the follower’s objective. When the arc costs are affine functions of the number of times they are interdicted, this problem is solvable by linear programming. However, when the cost functions are convex or when they are concave, we show that the expected costs are Schur concave or convex, respectively. This property allows us to prove that the problem becomes strongly NP-hard in the nonaffine case. We also propose several algorithms for this problem. Some are for special cases, and one is a general algorithm. We examine the efficacy of our algorithms on a test bed of randomly generated instances by comparing our algorithms to a standard solver.