A sequential algorithm for the bilevel network interdiction problem

Several attempts on network interdiction have been made by different authors in the past due to its application in military operations, supply chain management, prevention of illicit drug trade and other related areas. The problem is NP-complete and various techniques have been proposed for solving this problem. In this work we propose a greedy heuristic for the sequential disruption of edges in a network constrained by edge capacity. Because of a few shortcomings in this algorithm, we further include a stochastic component in the selection of edges. The solution was originally developed for the problem statement of the 8th AIMMS - MOPTA Optimization Modeling Competition and therefore, the applicability of the technique is shown on the network provided for the competition.