Publications -> Conference Papers

Optimal Interdiction of Illegal Network Flow


Authors: Q. Guo, B. An, Y. Zick, and C. Miao
Title: Optimal Interdiction of Illegal Network Flow
Abstract: Large scale smuggling of illegal goods is a long-standing 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.
Keywords: 
Conference Name: 25th International Joint Conference on Artificial Intelligence (IJCAI'16)
Location: New York City, USA
Publisher: AAAI Press
Year: 2016
Accepted PDF File: Optimal_Interdiction_of_Illegal_Network_Flow_accepted.pdf
Permanent Link: http://www.ijcai.org/Proceedings/16/Papers/357.pdf
Reference: Q. Guo, B. An, Y. Zick, and C. Miao, “Optimal interdiction of illegal network flow,” in Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI’16). AAAI Press, July 2016, pp. 2507–2513.
bibtex: 
@inproceedings{LILY-c86, 
    author	= {Guo, Qingyu and An, Bo and Zick, Yair and Miao, Chunyan},
    title	= {Optimal Interdiction of Illegal Network Flow},  
    booktitle	= {Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI'16)}, 
    year		= {2016}, 
    month	= {July}, 
    pages	= {2507-2513}, 
    location	= {New York City, USA},
    publisher	= {AAAI Press},
 }