A simulated annealing algorithm to the stochastic network interdiction problem

This paper proposes a solution algorithm for solving the stochastic network interdiction problem (SNIP). The problem is formulated as a two-stage stochastic integer program with an objective to minimize the expected maximum flow through the network, given that the success of interdicting an arc on the work is a Bernoulli random variable. The first-stage solution is obtained by using simulated annealing heuristic algorithm. In the second-stage problem, each scenario is a maximum network flow problem which is solved using the Ford-Fulkerson algorithm. The results show that our solution values of test instances are close to optimal. This is verified with a previous study in the literature that solved the same exact test instances and provided lower and upper bounds to their solutions. Furthermore, our average solution time is significantly lower.