Multi-Stage Network Interdiction with Decision-Dependent Success: Scenario Clustering and Reformulation Techniques

Abstract

This article studies a network interdiction problem where the success of the first player's attempt to remove arcs is based on decision- dependent success probabilities, and the second player (the follower) responds by pushing maximum flow. In this multi-stage model, previous interdictions affect future interdictions' success probabilities. The decision-dependent structure requires an objective function that includes a conditional probability that is nonlinear, which we reformulate into a mixed integer program using probability flow networks over all possible scenarios. However, this reformulation involves a large number of scenarios. To reduce the scenario space, we present a scenario clustering approach that exploits the problem structure while preserving optimality. We also provide a scenario clustering heuristic for further reductions and faster solution times where optimality is not guaranteed. We illustrate our method by solving instances on various physical grid and supply chain networks. We also investigate how changing decision-dependent success probabilities over time can influence interdiction policies over these networks.