Planetary Interceptor Assignment

Weapon-Target Assignment Problem (WTA)

Assign orbital defense lasers to incoming alien missiles to minimize expected damage to Earth. The WTA is NP-hard due to the nonlinear objective — each additional weapon assigned to the same target yields diminishing returns in survival probability reduction.

The Scenario

Orbital Defense

Earth's orbital defense grid consists of 3 laser platforms with limited ammunition and varying accuracy against different threat types. An incoming wave of 4 alien missiles has been detected, each with a different threat value reflecting the damage it would cause if it reaches Earth. The commander must decide how to allocate laser shots to missiles — assigning too many shots to one target wastes resources, while leaving a high-value target unengaged risks catastrophic damage.

Defense Domain	OR Element	Symbol	Example
Orbital laser	Weapon	i ∈ {1,...,m}	Laser Alpha (3 shots)
Alien missile	Target	j ∈ {1,...,n}	Mothership Scout (V=100)
Threat level	Target value	Vˇ	100 (mothership)
Hit chance	Kill probability	pᵢˇ	0.8
Ammo count	Weapon capacity	Wᵢ	3 shots
Assignment	Decision variable	xᵢˇ ∈ ℤ⁺	2 shots at target
Survival chance	Objective term	∏(1-p)ⁿ	0.04

Mathematical Model

WTA Formulation

MINIMIZE Σˇ Vˇ · Πᵢ (1 - pᵢˇ)^xᵢˇ subject to: Σˇ xᵢˇ ≤ Wᵢ ∀ i ∈ {1,...,m} // weapon i has Wᵢ shots xᵢˇ ∈ ℤ⁺ ∀ i,j // non-negative integer // Objective is nonlinear: the product (1-pᵢˇ)^xᵢˇ represents the // probability that target j survives all xᵢˇ shots from weapon i. // Multiple weapons engaging the same target: // survivalˇ = Πᵢ (1-pᵢˇ)^xᵢˇ // Expected damage = Σˇ Vˇ × survivalˇ

Why is this hard?

The WTA is NP-hard even for identical weapons (Manne, 1958). The nonlinear objective means we cannot use standard linear or integer programming solvers directly. A logarithmic transformation converts the product to a sum: log(Π(1-p)ⁿ) = Σ x·log(1-p), but the resulting problem remains a nonlinear integer program. Ahuja et al. (2007) developed exact branch-and-bound algorithms exploiting the problem’s structure, solving instances with 200 weapons and 200 targets.

Try It Yourself

Interactive Solver

★★☆ Heuristic (Greedy, MMR) ★★★ Exact (B&B, small instances)

Weapon-Target Assignment Solver

3 weapons (capacities 3, 2, 4) vs 4 targets (values 100, 80, 60, 40). Kill probabilities shown in the matrix below.

	T1 (100)	T2 (80)	T3 (60)	T4 (40)
Laser Alpha (3)	0.80	0.60	0.70	0.90
Laser Beta (2)	0.70	0.80	0.50	0.60
Ground Gamma (4)	0.60	0.50	0.80	0.70

Solution Methods

The Algorithms

1. Greedy by Threat Value ★★☆ Heuristic

O(n · m) per pass

Sort targets by value Vˇ descending. For each target, assign the weapon with the highest kill probability that still has capacity remaining. Simple and fast, but ignores diminishing returns from multiple engagements.

Sort all alien missiles by threat value (highest first)
For the highest-value unassigned target, find the laser with the best kill probability and remaining ammo
Assign one shot from that laser to that target
Repeat until all weapon capacity is exhausted or all targets are assigned

2. Maximum Marginal Return (MMR) ★★☆ Heuristic

O(n · m) per iteration, ΣWᵢ iterations total

At each step, evaluate every possible (weapon, target) pairing and choose the one yielding the largest marginal reduction in expected surviving value. This accounts for diminishing returns: adding a second shot to a target already engaged is less valuable than engaging a new target.

Compute current expected surviving value for all targets
For every (laser, missile) pair with remaining capacity, compute the marginal improvement from one additional shot
Select the pair with the maximum marginal reduction
Update survival probabilities and remaining capacity
Repeat until all capacity is exhausted

3. Branch & Bound (Exact) ★★★ Exact

O(Wⁿ) worst case — feasible for ≤5 weapons, ≤8 targets

Enumerate all feasible assignments using depth-first search with pruning. At each node, compute a lower bound on the expected surviving value using a relaxation. Prune branches that cannot improve on the current best solution. Guarantees optimality for small instances.

Root node: no assignments made, full weapon capacities
Branch: assign 0, 1, 2, ... shots from weapon i to target j
Bound: compute a lower bound by assuming remaining weapons can achieve their best possible kill rates
Prune: if lower bound ≥ current best, skip this subtree
Leaf: all weapons assigned — update best if improved

References

Published Manne, A.S. (1958). “A Target-Assignment Problem.” Operations Research, 6(3), 346–351. — Original formulation of the WTA as a nonlinear integer program.

Published Ahuja, R.K., Kumar, A., Jha, K.C., & Orlin, J.B. (2007). “Exact and Heuristic Algorithms for the Weapon-Target Assignment Problem.” Operations Research, 55(6), 1136–1146. — Branch-and-bound + network flow heuristics; solved 200×200 instances.

Preparing for First Contact

If the aliens arrive, we suspect you will not be visiting a GitHub Pages site. If they don't arrive, you have learned some excellent OR methods that transfer seamlessly to logistics optimization and resource allocation.

We do recommend the Hungarian algorithm. It works on any planet.

All Defense Applications GitHub

👽🛸⚠️

Educational Fiction Disclaimer

This is a fictional educational scenario.

All “alien invasion” content exists purely to teach Operations Research concepts
All data, scenarios, and parameters are entirely fictional
No actual military applications are intended or endorsed
The author advocates for peace and opposes militarization