Optimal Interdiction of Illegal Network Flow

1 Introduction

Stopping undesirable behavior on a network is a problem pertaining to many security domains: disruption of enemy supply chains, infectious disease control, and the interception of illegal goods such as drugs or weapons. Physical networks are typically defended via checkpoints: physical roadblocks or inspection points positioned at various points in the network. In all network interdiction scenarios, the objective of those defending the network is to minimize the amount of flow through the network. From a resource optimization perspective, this is an extremely challenging task. There are several factors interrelating here: first, defender resources are limited; second, placing a guard at some point on the network does not guarantee that any smuggler passing through will be caught - it merely increases the likelihood of a successful capture; finally, it is natural to assume that smugglers have prior knowledge of defenders' positioning via intelligence gathering. The defender is thus placed at a disadvantage: not only does she have limited capability to stop an attack, her agents' moves are also monitored; thus, smugglers may successfully evade checkpoints if these are constantly positioned in a predictable manner. Indeed, randomized allocation strategies are imperatively needed [GAO, 2009]. Our work addresses the following challenge:

Devise a formal methodology for guarding a large, complex network against undesirable flow, considering action observability and limited resources.

Our Contributions: In this paper, we introduce a novel Network Flow Interdiction Game (NFIG) model, where the defender allocates a fixed number of security resources on the network, while the adversary commits to a feasible network flow. To compute the optimal defender strategy, we first provide a standard minimax bilevel formulation and reformulate it as a linear program (LP). However, due to the huge number of constraints and variables caused by exponentially large numbers of defender strategies and network paths, the LP is hard to solve. To overcome the computational challenge, we propose a Column and Constraint Generation (CCG) algorithm, with the following key contributions: i) we show that the algorithm converges to the Stackelberg equilibrium with finite iterations; ii) we show the NP-hardness of the Column Generation subproblem, and provide several novel algorithms to solve it, including an exact compact convex nonlinear program and a greedy algorithm with constantfactor approximation guarantee; iii) we provide an exact compact convex nonlinear program for the Constraint Generation subproblem as well as a fast local search based heuristic algorithm; iv) extensive experimental evaluation shows that our CCG framework can scale up to realistic-sized NFIG instances and significantly outperform existing approaches.

Related Work: The network interdiction problem is well studied [Church et al., 2004]. In this model, we are given a weighted, directed or undirected graph, and our goal is minimizing the flow through the graph via deletion of edges/nodes (other goals - such as maximizing the shortest path, increasing detection probability - and other interdiction methods - such as decreasing edge capacity - have been studied as well [Altner et al., 2010; Ball et al., 1989; Israeli and Wood, 2002; Malik et al., 1989; Wood, 1993; Guo et al., 2016]. Other works study stochastic network interdiction where the interdiction action is successful with some known probability p [Pan et al., 2001; Pan, 2005]. However, none of them consider the randomized resource allocation strategy, i.e., the mixed strategy, due to the impossibility to change the resource allocation frequently, especially for interdiction actions such as destroying arcs. Moreover, randomized resource allocation is known to be necessary to improve the interdiction efficiency; for example, in the smuggling domain, checkpoint operation status can actually change daily [GAO, 2009]. However, randomization does lead to a drastic increase in problem complexity: while in the deterministic network interdiction model an adversary's strategy has a compact representation (as a network flow), it is not the case in our setting.

We model NFIG as a Stackelberg security game; security games try and find the optimal resource allocation to defend some valuable facility, based on game-theoretic methodologies [Tambe, 2011; Yin et al., 2014]. However, in standard security game models, attacker strategies are typically compactly representable (e.g. a distribution over possible targets) [An et al., 2013; Yin et al., 2015; Gan et al., 2015]. Some recent work proposes network security games [Tsai et al., 2010; Jain et al., 2011; 2013]; here, the defender allocates security resources on a (transportation) network and the attacker chooses a reliable path to escape, and both players have exponentially large strategy spaces; our model differs from these works in several important ways. Most importantly, our goal is minimizing the flow through a network, rather than preventing a single attacker from escaping; thus, the methodology proposed in existing works cannot be directly applied to our setting.

Motivating Domain: Our model is quite general, and can easily apply to various network security domains; to illustrate the underlying issues and motivation for our model choice, we now briefly present the problem in the context of stemming the drug flow through the US-Mexico border patrol. Figure 1 shows the major roads in the southern border area [GAO, 2009]. Drug smuggling in the southern border is dominated by 4 large well-organized and independent cartels: Sinaloa, Juarez, Gulf and Los Zetas, each of them controls the drug trafficking over 1000-mile border and has its own major area of influence in the United States [Beittel, 2015; Rosenberg, 2015]. These organizations typically use commercial, private and rental vehicles to smuggle illegal goods via land points of entry (sources). The goods travel along different paths on the road network to different destination cities (sinks) [DOJ, 2010; Rosenberg, 2015]. Traffickers typically choose multiple transport paths, in order to avoid raising obvious suspicion by the inspection stations, and to mitigate losses in case of capture [Steinrauf, 1991].

In 2009, the Border Patrol operated 39 tactical checkpoints with flexible and daily changeable operation status in the southern border, which are generally operated at fixed locations. However, due to the shortage of staff, canines and basic facilities (i.e. security resources), only few of them are actually operational [GAO, 2009]. With this limitation for tactical checkpoints, randomized allocation strategies of limited security resources are essential; smugglers have the ability to observe the operational status of checkpoints, and make their best decision on trafficking activities, such as the amount of drugs to move through different POEs and paths. Indeed, a testimony before Congress by the Arizona Attorney General, revealed the sophisticated surveillance and communication technologies used to monitor security vulnerabilities and adjust plans to increase the chance of success [Kibble, 2009].

2 Preliminaries

Our proposed NFIG models an attacker and a defender who take actions on a capacitated graph G = (V↪ E), with nodes set V and edges set E, and a capacity vector c, where capacity ce represents the maximum amount of adversary flow passing through edge e without arousing obvious suspicion by inspection facilities (permanent checkpoints, sensors, etc). We assume that the graph has a unique source node (POE) s 2 V and a unique sink node t 2 V (drug distribution city in smuggling scenario). The unique source/sink assumption is no loss of generality: a graph with multiple source nodes and sink nodes can be transformed into a single-source-sink graph by adding two new nodes s and t as the new unique source and sink nodes respectively, connecting s to each source node and t to each sink node with proper capacitated edges. Let P denote the set of all s-t paths in G. For a path p 2 P, we say node v 2 p (edge e 2 p) if p passes through v (e). Let I denote the set of all inspection stations, such as the tactical checkpoints in the border patrol scenario, and an inspection station is operated if the defender assigns a security resource on it, such as staffs, canines, and inspection facilities. Each station i 2 I is characterized by a location, either a node or an edge in the graph (with a bit abuse of notation, we use i interchangeable with its location, such that i 2 V [ E), and a constant parameter ⌧i 2 [0↪ 1] denoting the proportion of adversary flow interdicted at i when operated, i.e., inspection probability. For example, in the border patrol scenario, the officers at checkpoint i can conduct regular inspections on passing vehicles and an illegal trafficker will be caught with some probability ⌧i depending on the officers' experience, which can be treated as a constant factor. Let k < ♣I♣ be the number of security resources owned by the defender.

Strategies: A defender pure strategy S = hSii is an allocation of k security resources to k inspection stations, i.e., Pi2I Si = k, where Si 2 ¶0↪ 1♦ and Si = 1 indicates that the inspection station i is operated. The defender pure strategy space is denoted by S. A mixed defender strategy x = hxSi is a probability distribution over all pure strategies where xS denotes the probability that S is played. Let X denote the defender mixed strategy space.

An attacker strategy is a network flow f with fp representing the amount of adversary flow passing along path p 2 P. 1 In order to avoid raising obvious suspicion, a feasible attacker strategy must satisfy the capacity constraint on each edge. Let F denote the set of all feasible attacker strategies, i.e.,

Utility: Since the attacker aims at maximizing his successful drug flow while the defender wants to minimize it, we assume NFIG a zero-sum game. Given a pure defender strategy S and an attacker feasible flow f , the attacker's utility is the sum of successful flows on all paths, i.e., Ua(S↪ f) = Pp2P Φ(S↪ p)fp, where

and Φ(S↪ p) represents the proportion of adversary flow on path p not interdicted by the operated inspection stations given S. The defender utility is Ud(S↪ f ) = -Ua(S↪ f ).

Equilibrium: NFIG is a leader-follower game, for which the widely adopted solution concept is the Stackelberg equilibrium (SE). Let y(x) denote the best response flow against defender mixed strategy x. A strategy profile hx⇤ ↪ f ⇤ i forms an SE, if: i) f ⇤ = y(x⇤ ), and ii) Ud(x⇤ ↪ f ⇤ ) ≥ Ud(x↪ y(x)) for all x 2 X. With the zero-sum assumption, the SE can be obtained by the following minimax formulation:

Given a defender mixed strategy x and an attacker feasible flow f , the attacker's and defender's expected utilities are: Ua(x↪ f ) = PS2S xSUa(S↪ f ) and Ud(x↪ f ) = -Ua(x↪ f ).

Since X↪ F are convex sets, and Ua(x↪ f) is a linear function in x when fixing f and vice versa, according to von Neumann's minimax theorem [Nlkaido, 1954], we have:

A direct consequence of the minmax theorem, critical for our key solution approach (Section 3.2), is the equivalence of SE and the Nash equilibrium (NE), where x⇤ is the best response against f ⇤ and f ⇤ is also the best response against x⇤ .

3 Solution Approach

In this section, we first provide an LP formulation to compute the equilibrium based on the standard minimax formulation. Since this LP has exponentially large number of variables and constraints, we then propose a novel Column and Constraint Generation (CCG) to further improve the scalability.

1 Note that the compact representation f = hfei is infeasible in NFIG. Please see Section B of Online Appendix for the explanation available at: http://www.ntu.edu.sg/home/boan/papers/ IJCAI16 Flowinterdiction Appendix.pdf.

3.1 LP Formulation

We start from the standard minimax formulation for SE:

The objective in Eq.(5a) is the attacker's expected utility Ua(x↪ f). The bilevel minimax program (5) can be reformulated as a linear program by replacing the inner program with its dual, and the resulting linear program (LP) is as follows:

The dual solution with respect to inequality (6c) provides the equilibrium attacker flow f , defined over all paths in P.

3.2 Column and Constraint Generation

The linear program (6) is challenging to solve due to the exponentially large number of variables and constraints (♣S♣↪ ♣P♣). To address this challenge, we propose a novel algorithm called Column and Constraint Generation (CCG), and prove the correctness of the CCG algorithm based on the property that the SE of SNIG is the same as the NE (Section 2).

The algorithm CCG is sketched in Algorithm 1. Initially, a small space hS 0 ↪ P 0 i is generated with arbitrary candidate defender strategies and s-t paths. Then CCG solves a restricted version of NFIG with LP(S 0 ↪P 0 ), where the defender pure strategy space is S 0 and the attacker flow is restricted to paths only in P 0 , i.e., Eqs.(6a)-(6d) with hS↪Pi replaced by hS 0 ↪ P 0 i, and obtains primal and dual solutions (x↪ u↪ f ). This restricted NFIG can be solved efficiently since the game is very small. Obviously, the obtained primal solution x and dual solution f form an SE of the restricted NFIG, but not necessarily the original NFIG. Therefore, two subproblems ColG (Column Generation) and ConG (Constraint Generation) are proposed to generate useful defender pure strategies and s-t paths into hS 0 ↪P 0 i in order to guide the SE of the restricted NFIG to the one of the original NFIG. Respectively, ColG generates a defender strategy S 2 S which is a best response against f , and ConG generates an s-t path p 2 P with maximal reduced cost which measures the degree of violating inequality (6c).

The key of the CCG algorithm is that once ColG generates the pure strategy S already in S 0 , the current solution x of restricted NFIG is the defender best response against the adversary flow f in the original NFIG (PROPOSITION 1), and similarly, if ConG generates an s-t path p with non-positive reduced cost, the current equilibrium flow f of restricted NFIG is the attacker best response flow against x in the original NFIG (PROPOSITION 7). Therefore, the NE of the original

Algorithm 1: CCG Algorithm for NFIG

• 1 Initialize S 0 by generating arbitrary defender strategies; 2 Initialize P 0 by generating arbitrary s-t paths; 3 repeat 4 (x↪ u↪ f) LP(S 0 ↪P 0 ); 5 S ColG(f); 6 S 0 S 0 [ ¶S♦; 7 p ConG(x↪ u); 8 P 0 P 0 [ ¶p♦; 9 until convergence; 10 return (x↪ f).

NFIG is achieved when ColG generates a pure strategy S already in S 0 and ConG generates an s-t path p with nonpositive reduced cost. Since the NE is the same as the SE, the current solution pair (x↪ f ) forms the SE of the original NFIG.

Comparison with Double Oracle: The double oracle (DO) algorithm, first proposed byMcMahan et al. [2003], is a standard method for solving two-player zero-sum games with large scale strategy spaces, and is widely adopted by security game research [Jain et al., 2011; 2013; Vanek et al., 2012; Wang et al., 2016]. In DO, both players commit to mixed strategies. Thus, to apply DO to NFIG, the attacker's strategy is a probability distribution over all feasible flows, rather than a single flow. Besides, although the CoreLP of DO can be obtained from minimax formulation with the same manner as LP (6), each constraint is associated with a feasible flow (pure strategy) restricting the attacker's utility no smaller than that flow. Thus, a best-response flow is solved in DO's oracle, which is inefficient due to no compact representation of flows. As comparison, ConG solves an s-t path instead.

The central challenge and novelty of CCG is how to efficiently generate the pure defender strategies and s-t paths to add to S 0 and P 0 . Thus, we present the corresponding ColG and ConG algorithms in the following sections.

4 Column Generation (ColG)

This section concerns the ColG subproblem of Algorithm 1, which can be stated as follows: given an attacker feasible flow f defined over P 0 , generate the defender pure strategy S 2 S blocking the largest amount of flow, i.e., S = argmaxS02S Ud(S0 ↪ f). PROPOSITION 1 shows that once ColG generates the pure strategy S already in S 0 , the current equilibrium mixed strategy x of restricted NFIG is the best response against f of the original NFIG.

Proposition 1. If ColGgenerates the pure strategy S already in S 0 , the current equilibrium mixed strategy x of restricted NFIG is the best response against f of the original NFIG.

We conduct thorough analysis of ColG's computational complexity, and show that it is NP-hard for general graphs, while polynomial-time solvable for the tree-like networks. For the ease of reading, we put proofs of all propositions and theorems in Section A of Online Appendix1 .

Theorem 2. The ColG subproblem is NP-hard.

Algorithm 2: Greedy Algorithm for Column Generation

1 Initialize S0 = ;; 2 while ♣S0 ♣ < k do 3 i⇤ = arg maxi ◁2S0 :S0[¶i♦2S Ud(S0 [ ¶i♦↪ f ); 4 S0 = S0 [ ¶i⇤ ♦; 5 return S0 .

4.1 Convex Integer Nonlinear Formulation

Disregarding the NP-hardness of ColG subproblem, we provide a compact integer program, with nonlinear objective function Ua(S↪ f), to solve it exactly. The program is proved to be convex (PROPOSITION 4) and hence can be solved to optimality with many commercial solvers, like KNITRO.

Proposition 4. Given an attacker flow f 2 F, the objective function (7a) is convex over decision variable S 2 [0↪ 1]♣I♣ .

4.2 Greedy Algorithm

We also propose a polynomial-time greedy algorithm of computing the approximate best response defender pure strategy, as shown in Algorithm 2 (we slightly abuse notation and let S represent the set of operated inspection stations). Starting from an empty set S = ;, we iteratively assign a security resource on an inspection station i⇤ which brings the maximal marginal utility Ud(S [ ¶i♦↪ f ) - Ud(S↪ f ), until all k resources are assigned. The approximate pure strategy S0 of Algorithm 2 and the approximate mixed strategy x0 computed by CCG with ColG solved by Algorithm 2 are proved to achieve competitive ratios (THEOREMS 5 & 6).

Theorem 5. The utility of S0 obtained by Algorithm 2 is bounded by Ud(S0 ↪ f) - Ud(;↪ f) ≥ (1 - 1e )(Ud(S⇤ ↪ f) - Ud(;↪ f)), where S⇤ is the optimal solution for ColG.

Theorem 6. Let (x⇤ ↪ f ⇤ ) be the equilibrium solution of an NFIG, and let (x0 ↪ f 0 ) be the solution computed by CCG algorithm with ColG subproblem solved by greedy Algorithm 2. Then Ud(x0 ↪ f 0 )-Ud(;↪ f 0 ) ≥ (1- 1e )(Ud(x⇤ ↪ f ⇤ )-Ud(;↪ f 0 )).

5 Constraint Generation (ConG)

Given the optimal primal solution (x↪ u) of LP(S 0 ↪P 0 ), the ConG subproblem generates an s-t path p 2 P that has maximal reduced cost defined as: R(p) = PS2S 0 xSΦ(S↪ p) - Pe2p ue, i.e., p = maxp02P R(p0 ). Note that R(p)  0 if and only if inequality (6c) associated with p is satisfied by (x↪ u). We show that if ConG generates an s-t path p such that R(p)  0, the current equilibrium flow f of the restricted NFIG is the best response against x of the original NFIG.

Algorithm 3: VNS for ConG

1 Generate a random s - t path p; 2 p LocalSearch(p); 3 while no termination condition is met do 4 p0 randomly pick one from N l (p); 5 p0 LocalSearch(p0 ); 6 if R(p0 ) > R(p) then p p0 ; 7 if R(p) > 0 then return p

Proposition 7. If the ConG generates an s-t path p with nonpositive maximal reduced cost, the current equilibrium flow f of the restricted NFIG is the attacker best response pure strategy against x of the original NFIG.

5.1 Convex Integer Nonlinear Formulation

We first propose a compact convex integer program to solve the ConG problem exactly. Let binary variable γ 2 ¶0↪ 1♦♣V ♣+♣E♣ denote an s-t path p, such that for every node v 2 V and edge e 2 E, γv = 1 if v is on path p and γe = 1 if e is on path p. We say node v 2 e if edge e is adjacent with v. The convex formulation is as follows:

The convexity of the objective (8a) can be easily verified in the same way of proving PROPOSITION 4. Eqs.(8b)-(8e) ensure that γ denotes a feasible s-t path p in the sense that: i) s and t are on p (8e); ii) exactly one edge adjacent with s (t) is on p (8b); iii) if node v, except s and t, is on p, then exactly two edges adjacent with v are on p (8c); and iv) if node v is not on p, then no edge adjacent with v is on p (8c).

Notice that the program (8) without constraint (8d) can also solve the ConG subproblem exactly. The integer programs are usually solved with the popular branch and bound (B&B) framework and the efficiency of B&B depends on the quality of the upper bound obtained by solving the linear relaxation of the program (8). Thus, inequality (8d) is proposed to tighten the upper bound by cutting off some fractional solutions with too high objective values, such an example is γ with: i) γe = 1 for e0 = (s↪ v0 ), e00 = (v00 ↪ t); ii) γv = 0▷5 for v0 and v00 ; iii) γv = 0, γe = 0 for all other nodes and edges.

5.2 Variable Neighborhood Search (VNS)

Although the convex program (8) can solve the ConG subproblem exactly, it still cannot scale up to solve large scale networks. Observe, however, in each iteration of CCG algorithm, we actually need not find the path with maximal reduced cost; rather, any path with a large enough (positive) reduced cost would suffice. Thus, a fast heuristic search for

Algorithm 4: LocalSearch (p)

1 Repeat

2 p⇤ argmaxp02Nl(p) R(p0 ); 3 if R(p⇤ ) > R(p) then p p⇤ ; 4 else return p;

generating such paths is satisfactory for most iterations, except when the heuristic is unable to find a path with positive reduced cost. In this case we can call the convex program (8). To this end, we propose a heuristic search algorithm (Algorithm 3) based on Variable Neighborhood Search (VNS) framework [Hansen and Mladenovi´c, 2001].

Two key components of VNS are: i) N l (p), denoting the set of neighbor paths of p within distance l; and ii) LocalSearch (p) to find a local optimum starting from p (Algorithm 4). We say that path p0 is a neighbor path within distance l of p if p0 can be obtained by replacing a v0 -v00 sub-path of p with another v0 -v00 path of length no larger than l. The LocalSearch (p) iteratively searches for a neighbor path p⇤ with maximal reduced cost (Line 2) and updates current incumbent p if p⇤ is a better solution (Line 3), until a local optimum is obtained whose reduced cost is higher than all its neighbor paths.

After initialized with an arbitrary local optimum (Lines 12), the VNS randomly picks a neighbor path p0 of p and applies LocalSearch (p0 ) to find a local optimum (Lines 4-5). Afterwards, the incumbent p is updated. This loop is repeated until a termination condition is met: i) current incumbent p has a positive reduced cost (Line 7); or ii) for cmax consecutive iterations, the incumbent p is not updated.

6 Experimental Evaluation

We evaluate the performance of our approach through extensive experiments. We use CPLEX (version 12.6) to solve linear programs and KNITRO (version 9.0.0) to solve nonlinear programs. All computations were performed on a 64-bit PC with 16 GB RAM and a quad-core 3.4 GHz processor. All values are averaged over 40 instances unless otherwise specified. All random planar graphs are generated by the Waxman geographical model (WG) suitable for modeling highway networks [Waxman, 1988]. In the WGmodel, ♣N♣ nodes (cities) are placed in a rectangular domain uniformly, and each pair of nodes at Euclidean distance d is jointed by an edge with probability p = e-λd , where λ is a constant adjusted to achieve the desirable average degree D. The two nodes with maximal Euclidean distance are set as the source and sink nodes of graph G. By default, the instances are parameterized as follows: the number of inspection stations ♣I♣ = b↵(♣V ♣ + ♣E♣)c and the number of resources k = bβ(♣V ♣ + ♣E♣)c, where ↵ and β are tunable parameters. All inspection stations are randomly placed on the graph. The edge capacity ce is randomly chosen in [0↪ 10], and inspection probability ⌧i ⇠ [0▷4↪ 0▷6]. The l and cmax are set as 4 and ♣V ♣ respectively in VNS.

We compare the scalability of three versions of our algorithms: i) CCG: Algorithm 1 with ColG and ConG solved by programs (7) and (8); ii) CCG*: Algorithm 1, where ColG and ConG are first solved by greedy methods (Algorithms 2 and 3), and then call the programs (7) and (8) when greedy methods return a pure strategy S already in S 0 or path p with R(p)  0; iii) LP: the linear program (6), with the benchmark double oracle (DO) where two oracles solve the best response pure strategies (S, f) for both players [Jain et al., 2011].

To evaluate the solution quality of our approach, we implement three heuristic strategies as baselines. The quality of a solution x is measured by Ud(x↪ y(x)). The baseline mixed strategies are: i) DMU with marginal coverage probability of each inspection station equal to k ♣I♣ ; ii) DMT where marginal coverage probability of each inspection station is normalized inspection probability; iii) DMW where marginal coverage probability of each inspection station is normalized inspection weight. The inspection weight wi of station i is defined as the maximum amount of flow that i can interdict, i.e., the production of ⌧i and the maximum amount of flow passing through that edge or node; Given the marginal coverage probabilities, the defender mixed strategies are generated by the Combo Sampling algorithm [Tsai et al., 2010].

Scalability Analysis. We compare the scalability of our algorithms on WG graphs with varying degrees: D = 2▷86 which is the mean degree of road network [Gastner and Newman, 2006], and D 2 ¶2▷7↪ 3▷0♦. ↵ = 0▷3 and β = 0▷15. The results are depicted in Figures 2(a)-2(c), where DO cannot scale up to 50 nodes for D = 2▷7 and D = 2▷86 and 40 nodes for D = 3▷0 with runtime cap of 1800 seconds, while LP cannot scale up to 30 nodes with memory cap of 8GB. The results show that although our approaches (CCG,CCG*) involve nonlinear programs (7) and (8), they still outperform LP and DO significantly due to the compact representation. Besides, CCG* also outperforms CCG a lot which shows that the greedy methods (Algorithms 2 and 3) can obtain good enough solutions. Especially CCG* can scale up to realisticsized networks with 60 nodes and over 40 inspection stations and 20 resources, while the number of tactical checkpoints operated in the Southern border is 39 in 2009 [GAO, 2009].

Solution Quality Analysis. We also compare the solution qualities of our algorithms with three baseline strategies on WG graphs with varying degrees (↵ = 0▷3 and β = 0▷15), demonstrated by Figures 2(f)-2(h). It is clear that CCG* outperforms these baselines significantly. Besides, the baseline DMW works best among the three baselines since the inspection weights well measure the capability of inspection stations. Note that the numbers of inspection stations and resources are proportional with the network size, and hence there exists no monotone relationship between utility and network size.

Varying Values of ↵ and β. Figures 2(d)-2(e) show the solution qualities of CCG* and three baselines on WG graphs (♣V ♣ = 40, D = 2▷86) with varying values of ↵ and β, from which we can see: i) with fixed β, increasing ↵ improves the defender utility for more available inspection stations; ii) with fixed ↵, increasing β also improves the defender utility for more available resources. Moreover, CCG* outperforms these baselines significantly for all tested values of ↵ and β.

Robustness. In reality, the attacker might not have perfect observation on the defender strategy. Thus, we compare the solution qualities of CCG* and baselines on WG graphs (♣V ♣ = 40, D = 2▷86, ↵ = 0▷3 and β = 0▷15) with the attacker's estimation x0 of the defender strategy x randomly generated by: x0 = ˜x◁♣˜x♣ where ˜xS ⇠ xS · [1-δ↪ 1+δ]. The solution quality of x is measured by Ud(x↪ f 0 ) with f 0 being the attacker best response against x0 . The result is depicted in Figure 2(i) with δ = 20%, and the result shows that our approach CCG* is robust enough and outperforms baselines significantly under a high level of observation uncertainty.

Application on Southern Border Network. We also conduct experiments on two sectors in Southern Border Patrol: Laredo and San Diego sectors. Please see Section C of Online Appendix1 for details of these sectors. The results are depicted in Figure 2(j), showing that our approach significantly outperforms the baseline methods for the realistic networks.

7 Conclusion

This paper studies the problem of optimally interdicting an illegal network flow. We introduce a novel Stackelberg game model called NFIG, and propose a Column and Constraint Generation (CCG) algorithm to solve it. The computational complexity of its ColG subproblem is analyzed. Several novel algorithms are provided to solve the two subproblems including convex optimization, 1 - 1e approximation method and a heuristic search algorithm. Experimental evaluation shows that CCG scales up to realistic-sized networks and significantly outperforms existing methods and heuristics.

Acknowledgements

This research is supported by NRF2015NCR-NCR003-004, the National Research Foundation, Prime Minister's Office, Singapore under its IDM Futures Funding Initiative. The authors would like to thank the anonymous reviewers for their helpful comments.