Stochastic Maximum Flow Network Interdiction with Endogenous Uncertainty

Abstract

We describe the two-stage maximum flow network interdiction problem under endogenous stochastic interdiction. Our model consists of two agents playing a Stackelberg game. A smuggler who wishes to maximize the expected flow of some illegal commodities that can be transmitted between a source and a sink without being detected. On the other hand, an attacker tries to minimize the flow of drugs by installing some detectors or adding some security controls on critical arcs to increase the probability of detection. We consider a stochastic program under endogenous uncertainty in which the interdictor’s decisions can alter the probability of detection. The problem can be formulated as a bilevel program in which the attacker, having a limited budget, chooses critical arcs to install detectors and enhances the interdiction probability of those arcs. The bottom level problem is a two-stage problem to maximize the flow in the network by smugglers. A bilevel decomposition algorithm has been applied to solve the problem by adding some Benders’ cuts iteratively. We applied a successive method, to deal with non-linearity arising in the probability measure of each path. A case study of drug trafficking network is applied to recognize which countries have the most significant effect in interdicting the drug trafficking network. The police can concentrate on those areas to decrease drug flow. Our results demonstrate that if the critical arcs are chosen wisely to enhance and the probability of opium seizers decrease slightly, a significant reduction in the expected total flow of drugs can be achieved.

Keywords

• network interdiction
• maximum flow
• endogenous uncertainty
• benders’ decomposition
• stackelberg game