Name
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. |
Year | Venue | Field |
|---|---|---|
2016 | IJCAI | Flow network,Column generation,Heuristic,Constraint generation,Computer science,Baseline (configuration management),Operations research,Interdiction,Stackelberg competition |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
6 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Qingyu Guo | 1 | 11 | 4.94 |
| Bo An | 2 | 892 | 106.05 |
| Yair Zick | 3 | 143 | 22.98 |
| Chunyan Miao | 4 | 2307 | 195.72 |