Optimal Interdiction of Illegal Network Flow

• Main Authors: Guo, Qingyu, Zick, Yair, Miao, Chunyan, An, Bo
• Other Authors: School of Computer Science and Engineering
• Format: Conference or Workshop Item
• Language: English
• Published: 2016
• Online Access: https://hdl.handle.net/10356/84604; http://hdl.handle.net/10220/41872; http://www.ijcai.org/Abstract/16/357
• Institution: Nanyang Technological University

Large scale smuggling of illegal goods is a longstanding problem, with $1.4b and thousands of agents assigned to protect the borders from such activity in the US-Mexico border alone. Illegal smuggling activities are usually blocked via inspection stations or ad-hoc checkpoints/roadblocks. Security resources are insufficient to man all stations at all times; furthermore, smugglers regularly conduct surveillance activities. This paper makes several contributions toward the challenging task of optimally interdicting an illegal network flow: i) A new Stackelberg game model for network flow interdiction; ii) A novel Column and Constraint Generation approach for computing the optimal defender strategy; iii) Complexity analysis of the column generation subproblem; iv) Compact convex nonlinear programs for solving the subproblems; v) Novel greedy and heuristic approaches for subproblems with good approximation guarantee. Experimental evaluation shows that our approach can obtain a robust enough solution outperforming the existing methods and heuristic baselines significantly and scale up to realistic-sized problems.