Reducibility
Glossary Contents
← Ch XIII
Chapter XIV Exact Cover
Ch XV →
  1. 40 — Exactly once
  2. 41 — Algorithm X in Ruby
  3. 42 — Crew assignment, exactly
42

Crew assignment, exactly

Set partitioning IPs are exact cover with costs. Every airline, freight carrier, and ride-share platform solves giant ones every night.

In airline operations, each flight leg has to be flown by exactly one crew — not zero (cancellation), not two (cost). The set of legal pairings (multi-day crew tours) is enormous; picking a subset where each leg is covered exactly once and total cost is minimized is the set partitioning problem, the cost-minimizing version of exact cover. American Airlines' 1989 PROBE solver saved them a reported $20M/year in 1989 dollars on crew assignment — about $53M/year in 2026 USD after inflation. The same template runs in meal-planning logistics (each ingredient appears in exactly one recipe of the week), factory line scheduling (each machine slot occupied by exactly one job), and Sudoku solvers in everyday newspapers — all built on Algorithm X or its industrial-strength descendants.

In plain terms

If you have to assign one and only one crew to each flight today, no flights left uncovered and no crew double-booked, you're partitioning the flights into crew tours. That partitioning is exact cover.

Scan to come back to page 42

End of Chapter XIV
Chapter XV Hitting Set →
← 41 Algorithm X in Ruby
3/3 · 42/63
43 Hit them all →