A minimum cost k-reliable network interdiction model

This paper proposes a model, named “a minimum cost k-reliable network interdiction”, which minimizes the cost of setting sensors on arcs for preventing any potential threat to a protected area. Mathematically, given any directed graph with a source and a sink, several arcs need to be selected such that any path from source to sink contains at least k arcs in the selected arcs with as few resources as possible. The original model is transferred to a bilevel formulation because it is nearly impossible to be exhibited explicitly, even for the network of a moderate size. This paper also proposes an approach for resolving a bilevel program where the lower level program is a mixed integer program. A small numerical example illustrates the feasibility of our model.