Interdiction

Author

CVXPY Developers and Balasubramanian Narasimhan

Introduction

This example is adapted from the CVXPY interdiction notebook. We explore a game between a smuggler moving through a directed graph and a security team trying to catch him.

Topic references:

Boyd, S. and Vandenberghe, L. Convex Optimization. Cambridge University Press.
Additional Exercise 15.4: Allocation of interdiction effort.
Shortest path problem in graph theory.

Problem Setup

The smuggler moves along a directed graph with $n$ nodes and $m$ edges from a source node to a destination node. Edge $j$ has evasion probability $p_{j}$ , which is the probability that the smuggler moves along that edge undetected. The probability that the smuggler makes it to the destination undetected is $\prod_{j \in P} p_{j}$ , where $P$ is the set of edges on the smuggler’s path.

The security team can control the evasion probabilities through allocation of resources. Their goal is to choose evasion probabilities to minimize the chance that the smuggler gets through undetected.

Formulation

Taking the logarithm of all probabilities, let $c_{j} = \log (p_{j})$ . The smuggler’s path evasion probability in log-space is $\sum_{j \in P} c_{j}$ .

We denote possible paths with a decision variable $x \in [0, 1]^{m}$ , where $x_{j} = 1$ denotes that edge $j$ is on the path. The smuggler’s problem (as an LP relaxation) is:

$\begin{array}{ll} maximize & c^{T} x \\ subject to & A_{inc} x = b, 0 \leq x \leq 1, \end{array}$

where $A_{inc}$ is the node-edge incidence matrix and $b$ encodes the source-to-sink flow constraint.

Using LP duality, the security team’s problem becomes:

$\begin{array}{ll} minimize & ν^{T} b \\ subject to & A_{inc}^{T} ν \geq c, c \in C, \end{array}$

where $ν$ is the dual variable and $C$ represents constraints on the edge evasion probabilities.

Helper Functions

We define helper functions for generating random geometric graphs and for finding optimal paths using igraph.

## Form an N x N grid of nodes, perturb positions, and connect nearby nodes
form_graph <- function(N, mu, eta, seed = NULL) {
    if (!is.null(seed)) set.seed(seed)
    mu <- mu / (N - 1)
    eta <- eta / (N - 1)

    ## Generate perturbed grid positions
    grid <- expand.grid(
        x = seq(0, 1, length.out = N),
        y = seq(1, 0, length.out = N)
    )
    pos <- data.frame(
        x = grid$x + mu * rnorm(nrow(grid)),
        y = grid$y + mu * rnorm(nrow(grid))
    )
    n <- nrow(pos)

    ## Connect nodes within distance eta (random geometric graph)
    d <- as.matrix(dist(pos))
    pairs <- which(d <= eta & upper.tri(d), arr.ind = TRUE)
    ## Both directions for a directed graph: (i->j) and (j->i) for each pair
    edges <- c(t(rbind(pairs, pairs[, 2:1, drop = FALSE])))

    G <- make_graph(edges, directed = TRUE, n = n)
    list(G = G, pos = pos, n = n)
}

## Generate random evasion probabilities for edges
## (same probability in both directions for symmetric pairs)
get_edge_probs <- function(G, seed = NULL) {
    if (!is.null(seed)) set.seed(seed)
    el <- as_edgelist(G)
    ## Create canonical key for each edge (smaller node first)
    keys <- paste(pmin(el[, 1], el[, 2]), pmax(el[, 1], el[, 2]), sep = "-")
    unique_keys <- unique(keys)
    ## Assign random probability to each unique edge pair
    vals <- setNames(runif(length(unique_keys)), unique_keys)
    as.numeric(vals[keys])
}

## Find optimal smuggler path using shortest path (Dijkstra)
opt_path <- function(G, p) {
    p <- pmin(p, 1)
    w <- -log(p)
    E(G)$weight <- w
    sp <- shortest_paths(G, from = 1, to = vcount(G), output = "epath")
    path_edges <- sp$epath[[1]]

    x <- rep(0, ecount(G))
    x[as.integer(path_edges)] <- 1
    x
}

Smuggler’s Path Example

We create a $10 \times 10$ grid graph with small perturbations. The evasion probabilities are distributed as $p_{j} = e^{- a_{j}}$ where $a_{j} \sim Uniform (0, 1)$ .

N <- 10
graph_data <- form_graph(N, mu = 0.12, eta = 1.2, seed = 5)
G <- graph_data$G
pos <- graph_data$pos
n <- graph_data$n

a <- get_edge_probs(G, seed = 2)
p <- exp(-a)

We solve the smuggler’s relaxed LP to find the optimal path from node 1 (upper-left) to node $n$ (lower-right).

## Build the incidence matrix
el <- as_edgelist(G)
m <- nrow(el)
A_inc <- matrix(0, nrow = n, ncol = m)
A_inc[cbind(el[, 1], 1:m)] <- -1   # tail (outgoing)
A_inc[cbind(el[, 2], 1:m)] <-  1   # head (incoming)

b <- rep(0, n)
b[1] <- -1       # source
b[n] <- 1        # sink

c_log <- log(p)

## Solve smuggler's LP
x_var <- Variable(m)
constraints <- list(A_inc %*% x_var == b, x_var >= 0, x_var <= 1)
prob <- Problem(Maximize(t(c_log) %*% x_var), constraints)
result_smuggler <- psolve(prob)

x_smuggler <- as.numeric(value(x_var))

cat(sprintf("Problem status: %s\n", status(prob)))
evasion_prob_lp <- exp(sum(x_smuggler * c_log))
cat(sprintf("Evasion probability of smuggler's optimal path: %e (%.3f%%)\n",
            evasion_prob_lp, evasion_prob_lp * 100))

Problem status: optimal
Evasion probability of smuggler's optimal path: 1.076744e-02 (1.077%)

We verify using Dijkstra’s algorithm (via igraph) on the same graph.

x_dijkstra <- opt_path(G, p)
evasion_dijkstra <- exp(sum(x_dijkstra * c_log))
cat(sprintf("Evasion probability via Dijkstra: %e (%.3f%%)\n",
            evasion_dijkstra, evasion_dijkstra * 100))

Evasion probability via Dijkstra: 1.076744e-02 (1.077%)

The LP relaxation and the graph-theoretic shortest path give the same optimal evasion probability.

Visualization

We plot the graph with edges colored by evasion probability, and highlight the smuggler’s optimal path.

## Create a data frame for edges
edge_df <- data.frame(
    x1 = pos$x[el[, 1]],
    y1 = pos$y[el[, 1]],
    x2 = pos$x[el[, 2]],
    y2 = pos$y[el[, 2]],
    prob = p,
    on_path = x_dijkstra > 0.1
)

ggplot() +
    ## Draw all edges (faded)
    geom_segment(data = edge_df,
                 aes(x = x1, y = y1, xend = x2, yend = y2, color = prob),
                 linewidth = 0.5, alpha = 0.3) +
    ## Draw path edges (bold)
    geom_segment(data = edge_df[edge_df$on_path, ],
                 aes(x = x1, y = y1, xend = x2, yend = y2, color = prob),
                 linewidth = 2) +
    scale_color_gradient(low = "red", high = "green",
                         name = "Evasion\nProbability") +
    ## Draw nodes
    geom_point(data = pos, aes(x = x, y = y), color = "white",
               size = 2, shape = 21, fill = "white", stroke = 0.5) +
    ## Highlight source and destination
    geom_point(data = pos[1, ], aes(x = x, y = y),
               color = "green", size = 5, alpha = 0.4) +
    geom_point(data = pos[n, ], aes(x = x, y = y),
               color = "red", size = 5, alpha = 0.4) +
    coord_equal() +
    theme_void() +
    theme(legend.position = "right")

Graph with evasion probabilities and smuggler’s optimal path

Security’s Objective

The security team’s goal is to allocate resources to minimize the smuggler’s evasion probability. With evasion probabilities modeled as $p_{j} = e^{- a_{j} r_{j}}$ , where $r_{j} \geq 0$ is the effort allocated to edge $j$ , the security problem (using LP duality) is:

$\begin{array}{ll} minimize & ν^{T} b \\ subject to & A_{inc}^{T} ν \geq - a \circ r \\ \sum_{j} r_{j} = m, 0 \leq r_{j} \leq R \\ B r = 0, \end{array}$

where $B$ enforces that symmetric edges have equal evasion probabilities, and $R$ is the maximum per-edge budget.

## Build B matrix for symmetry constraints
## For each pair of edges (i,j) and (j,i), enforce equal allocation
fwd <- which(el[, 1] < el[, 2])
rev_idx <- match(paste(el[fwd, 2], el[fwd, 1]),
                 paste(el[, 1], el[, 2]))
## Keep only pairs where the reverse edge exists
has_rev <- !is.na(rev_idx)
fwd <- fwd[has_rev]
rev_idx <- rev_idx[has_rev]

if (length(fwd) > 0) {
    B <- matrix(0, nrow = length(fwd), ncol = m)
    B[cbind(seq_along(fwd), fwd)] <- 1
    B[cbind(seq_along(fwd), rev_idx)] <- -1
} else {
    B <- matrix(0, nrow = 1, ncol = m)
}

## Solve security team's problem with R_max = 5
R_max <- 5
nu <- Variable(n)
r <- Variable(m)
constraints_sec <- list(
    t(A_inc) %*% nu >= -multiply(a, r),
    sum(r) == m,
    r >= 0,
    B %*% r == 0,
    r <= R_max
)

Warning: `multiply()` is deprecated. Use `x * y` instead.
This warning is displayed once per session.

prob_sec <- Problem(Minimize(t(b) %*% nu), constraints_sec)
result_sec <- psolve(prob_sec)

nu_val <- as.numeric(value(nu))
r_val <- as.numeric(value(r))

evasion_security <- exp(sum(nu_val * b))
cat(sprintf("Evasion probability with optimal resource allocation: %e\n", evasion_security))
cat(sprintf("Improvement factor over uniform allocation: %.2f\n",
            evasion_prob_lp / evasion_security))

Evasion probability with optimal resource allocation: 9.626215e-09
Improvement factor over uniform allocation: 1118554.37

Optimized Evasion Probabilities

p_opt <- exp(-a * r_val)

edge_df_opt <- data.frame(
    x1 = pos$x[el[, 1]],
    y1 = pos$y[el[, 1]],
    x2 = pos$x[el[, 2]],
    y2 = pos$y[el[, 2]],
    prob = p_opt
)

ggplot() +
    geom_segment(data = edge_df_opt,
                 aes(x = x1, y = y1, xend = x2, yend = y2, color = prob),
                 linewidth = 1) +
    scale_color_gradient(low = "red", high = "green",
                         name = "Evasion\nProbability") +
    geom_point(data = pos, aes(x = x, y = y), color = "white",
               size = 2, shape = 21, fill = "white", stroke = 0.5) +
    geom_point(data = pos[1, ], aes(x = x, y = y),
               color = "green", size = 5, alpha = 0.4) +
    geom_point(data = pos[n, ], aes(x = x, y = y),
               color = "red", size = 5, alpha = 0.4) +
    coord_equal() +
    theme_void() +
    theme(legend.position = "right")

Edge evasion probabilities after optimal resource allocation

Smuggler’s Optimal Path Under Optimized Security

We use Dijkstra’s algorithm to find the smuggler’s optimal path under the optimized resource allocation.

x_opt_path <- opt_path(G, p_opt)
c_opt <- log(p_opt)
evasion_opt_path <- exp(sum(x_opt_path * c_opt))
cat(sprintf("Evasion probability of smuggler's optimal path: %e\n", evasion_opt_path))

Evasion probability of smuggler's optimal path: 9.626215e-09

edge_df_opt$on_path <- x_opt_path > 0.1

ggplot() +
    geom_segment(data = edge_df_opt,
                 aes(x = x1, y = y1, xend = x2, yend = y2, color = prob),
                 linewidth = 0.5, alpha = 0.3) +
    geom_segment(data = edge_df_opt[edge_df_opt$on_path, ],
                 aes(x = x1, y = y1, xend = x2, yend = y2, color = prob),
                 linewidth = 2) +
    scale_color_gradient(low = "red", high = "green",
                         name = "Evasion\nProbability") +
    geom_point(data = pos, aes(x = x, y = y), color = "white",
               size = 2, shape = 21, fill = "white", stroke = 0.5) +
    geom_point(data = pos[1, ], aes(x = x, y = y),
               color = "green", size = 5, alpha = 0.4) +
    geom_point(data = pos[n, ], aes(x = x, y = y),
               color = "red", size = 5, alpha = 0.4) +
    coord_equal() +
    theme_void() +
    theme(legend.position = "right")

Smuggler’s optimal path under optimized security allocation

The optimal resource allocation makes the smuggler’s evasion probability dramatically smaller than the uniform allocation.

Session Info

R version 4.5.2 (2025-10-31)
Platform: aarch64-apple-darwin20
Running under: macOS Tahoe 26.3

Matrix products: default
BLAS:   /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRblas.0.dylib 
LAPACK: /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRlapack.dylib;  LAPACK version 3.12.1

locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8

time zone: America/Los_Angeles
tzcode source: internal

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] igraph_2.2.2  ggplot2_4.0.2 CVXR_1.8.1   

loaded via a namespace (and not attached):
 [1] gmp_0.7-5.1        generics_0.1.4     clarabel_0.11.2    slam_0.1-55       
 [5] lattice_0.22-9     digest_0.6.39      magrittr_2.0.4     evaluate_1.0.5    
 [9] grid_4.5.2         RColorBrewer_1.1-3 fastmap_1.2.0      jsonlite_2.0.0    
[13] Matrix_1.7-4       ECOSolveR_0.6.1    backports_1.5.0    scs_3.2.7         
[17] Rmosek_11.1.1      scales_1.4.0       codetools_0.2-20   cli_3.6.5         
[21] rlang_1.1.7        Rglpk_0.6-5.1      withr_3.0.2        yaml_2.3.12       
[25] otel_0.2.0         tools_4.5.2        osqp_1.0.0         Rcplex_0.3-8      
[29] checkmate_2.3.4    dplyr_1.2.0        gurobi_13.0-1      vctrs_0.7.1       
[33] R6_2.6.1           lifecycle_1.0.5    htmlwidgets_1.6.4  pkgconfig_2.0.3   
[37] cccp_0.3-3         pillar_1.11.1      gtable_0.3.6       glue_1.8.0        
[41] Rcpp_1.1.1         xfun_0.56          tibble_3.3.1       tidyselect_1.2.1  
[45] knitr_1.51         dichromat_2.0-0.1  highs_1.12.0-3     farver_2.1.2      
[49] htmltools_0.5.9    labeling_0.4.3     rmarkdown_2.30     piqp_0.6.2        
[53] compiler_4.5.2     S7_0.2.1

References

Boyd, S. and Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Boyd, S. and Vandenberghe, L. Additional Exercise 15.4: Allocation of interdiction effort.