Defense Unit Task Allocation
Generalized Assignment Problem (GAP)
Assign heterogeneous defense units to shield generator locations across the city. Each unit has different effectiveness and resource consumption at each location, and each location has limited capacity. Maximize total defensive effectiveness — a classical GAP, NP-hard in general.
Shield Generator Defense
| Defense Domain | OR Element | Symbol | Example |
|---|---|---|---|
| Defense unit | Item (agent) | i ∈ {1,...,6} | Mech-A |
| Shield location | Bin (task) | j ∈ {1,...,3} | North Shield |
| Combat effectiveness | Value | vᵢˇ | 8 |
| Energy/space used | Weight | wᵢˇ | 4 |
| Station power limit | Capacity | Cˇ | 10 |
| Deploy decision | Binary variable | xᵢˇ ∈ {0,1} | 1 = assigned |
Why is this hard?
The GAP generalizes the knapsack problem: each location is a knapsack with its own capacity, and items have location-dependent values and weights. Even with a single location (one knapsack), the problem is NP-hard. With multiple locations, the assignment constraint (each unit to at most one location) adds combinatorial structure that makes it harder still. The LP relaxation is typically tight enough to guide heuristics but may have a non-zero integrality gap.
Assignment Optimizer
★★☆ HeuristicValue matrix (effectiveness) and weight matrix (energy consumption):
| North | Central | South | |
|---|---|---|---|
| Mech-A | 8 | 5 | 6 |
| Mech-B | 7 | 9 | 4 |
| Tank-C | 6 | 7 | 8 |
| Drone-D | 5 | 3 | 9 |
| Infantry-E | 4 | 8 | 3 |
| Sniper-F | 9 | 4 | 7 |
| North | Central | South | |
|---|---|---|---|
| Mech-A | 4 | 3 | 5 |
| Mech-B | 5 | 4 | 3 |
| Tank-C | 6 | 5 | 4 |
| Drone-D | 3 | 2 | 6 |
| Infantry-E | 2 | 4 | 2 |
| Sniper-F | 5 | 3 | 4 |
The Algorithms
1. Greedy by Value-to-Weight Ratio
For each (unit, location) pair, compute the ratio vᵢˇ/wᵢˇ. Sort all pairs by ratio descending. Assign greedily: accept the assignment if the unit is unassigned and the location has remaining capacity.
- Compute vᵢˇ/wᵢˇ for all 18 pairs
- Sort by ratio descending
- For each pair: if unit i unassigned AND wᵢˇ ≤ remaining capacity of j, assign
- Stop when all units assigned or no feasible pair remains
2. LP Relaxation + Rounding
Relax xᵢˇ ∈ {0,1} to xᵢˇ ∈ [0,1]. Solve the continuous LP (here via a simplified greedy LP approximation). Round fractional solutions. The LP value is an upper bound on the true integer optimum; the gap shows how much the rounding costs.
- Allow fractional assignments xᵢˇ ∈ [0,1]
- Fill each location with highest-ratio fractional amounts up to capacity
- LP value = upper bound on integer optimal
- Round: assign each unit to the location where it has the largest fractional assignment
- Repair any capacity violations by removing lowest-value assignments
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