Optimal Interdiction of Illegal Network Flow
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 r...
Saved in:
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| 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 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | 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. |
|---|