---
title: "Optimal Interdiction of Illegal Network Flow"
authors:
  - "Qingyu Guo"
  - "Bo An"
  - "Yair Zick"
  - "Chunyan Miao"
doi: ""
url: "https://ijcai.org/proceedings/2016/357"
pdf: "https://ijcai.org/proceedings/2016/0357.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "2507-2512"
track: ""
keywords:
---

# Optimal Interdiction of Illegal Network Flow

Qingyu Guo, Bo An, Yair Zick, Chunyan Miao

*Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*, pages 2507-2512.

## 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.