Alien Supply Line Interdiction
Bi-Level Shortest-Path Network Interdiction
Block alien reinforcement routes to isolated Earth outposts by destroying key transit relays. The defender (leader) removes up to k arcs; the attacker (follower) then finds the shortest remaining path. This max-min structure makes it a bi-level optimization problem.
The Scenario
Supply Route Disruption
⚠ Educational context: This toy example is designed for educational clarity. Real network interdiction problems involve orders of magnitude more complexity and are subject to strict legal and ethical review.
An alien supply chain runs through a network of 6 relay stations connecting their forward base to an isolated Earth outpost. Earth's defense force can destroy up to k = 2 relay links. The goal: choose which 2 arcs to interdict so that the alien's shortest remaining supply route is maximized — buying time for evacuation.
| Defense Domain | OR Element | Symbol |
|---|---|---|
| Alien supply base | Source node | s = AlienBase |
| Earth outpost | Sink node | t = EarthOutpost |
| Transit relay | Intermediate node | Relay1, Junction, ... |
| Supply route | Arc with cost | (i,j) with cᵢˇ |
| Disruption budget | Interdiction limit | k = 2 |
// Bi-Level Formulation (Israeli & Wood, 2002):
MAXIMIZE (leader/defender)
MINIMIZE (follower/attacker) Σ(i,j)∈A cᵢˇ · fᵢˇ
follower subject to:
Σj fᵢˇ - Σj fˇᵢ = bᵢ ∀ i // flow conservation
where bᵢ = 1 if i=s, -1 if i=t, 0 otherwise
0 ≤ fᵢˇ ≤ 1 - xᵢˇ // arc removed if interdicted
leader subject to:
Σ xᵢˇ ≤ k // interdiction budget
xᵢˇ ∈ {0,1}
// Single-level MIP reformulation (via LP duality of follower):
MAXIMIZE πₜ - πₛ
πˇ - πᵢ ≤ cᵢˇ + Mᵢˇ·xᵢˇ ∀(i,j) // dual + big-M
Σ xᵢˇ ≤ k
// ⚠ Mᵢˇ must = (longest simple s-t path) - cᵢˇ + 1
// NOT an arbitrary large number (causes numerical issues)
Interactive Solver
Network Interdiction
★★★ Exact (enumeration, small k)
★★☆ Heuristic (greedy)
6-Node Network · Budget k=2
Enumerate all C(7,2) = 21 arc pairs. Find the interdiction that maximizes the attacker's shortest remaining path.
References
Published Israeli, E. & Wood, R.K. (2002). “Shortest-path network interdiction.” Networks, 40(2), 97–111. — Bi-level formulation + single-level MIP via LP duality.
Published Wood, R.K. (2011). “Bilevel Network Interdiction Models.” Wiley Encyclopedia of Operations Research. — Survey of interdiction formulations and extensions.
Published Cormican, K.J., Morton, D.P., & Wood, R.K. (1998). “Stochastic network interdiction.” Operations Research, 46(2), 184–197. — Extension to uncertain arc capacities.
Preparing for First Contact
If the aliens arrive, we suspect you will not be visiting a GitHub Pages site. We do recommend the Hungarian algorithm. It works on any planet.
Educational Fiction Disclaimer
This is a fictional educational scenario.
- All “alien invasion” content exists purely to teach OR concepts
- All data and parameters are entirely fictional
- No actual military applications are intended or endorsed
- The author advocates for peace and opposes militarization