Reducibility
Glossary Contents
← Ch III
Chapter IV Set Packing
Ch V →
  1. 10 — Disjoint or bust
  2. 11 — Branch-and-bound in Python
  3. 12 — Crew pairings
12

Crew pairings

Every airline in the world solves a giant set-packing problem before tomorrow's schedule prints.

An airline crew pairing is a sequence of flights one crew can fly together starting and ending at base — the set of flight legs they cover. The flying schedule has thousands of legs; the universe of legal pairings is millions. Each leg must be flown exactly once (which makes it a partitioning, the equality-constrained variant of packing), and the airline wants the cheapest valid combination. Delta, United, and Lufthansa run column generation LPs that produce promising pairings on demand and feed them into a set partitioning master problem — set packing's cousin. The same template covers vehicle scheduling, hospital nurse rostering, and ride-share driver-shift assignment. Saving 1% on crew costs at a major US carrier is on the order of $30M a year (2026 USD).

In plain terms

An airline has lots of flights to staff. It builds many possible "tours" a crew could fly, then picks a combination of tours that covers every flight exactly once and is cheapest. The math problem under the hood is set packing.

Scan to come back to page 12

End of Chapter IV
Chapter V Vertex Cover →
← 11 Branch-and-bound in Python
3/3 · 12/63
13 Touch every edge →