Introduction

An airline publishes a timetable: thousands of flight legs (a leg is one takeoff-to-landing hop) per day. Each leg needs a crew. But a crew cannot simply be bolted to one flight: it must start and end at its home base, may only fly so many hours in a duty period, needs legal rest between duties, and needs enough time on the ground to change aircraft. A chain of legs that obeys all of these rules, starts and ends at a base, and spans one to a few days is called a pairing (or rotation).

The crew pairing problem asks: from all legal pairings, choose a set that flies every leg exactly once at minimum total cost. Crew pay and hotels are usually quoted as the second-largest operating cost of an airline, after fuel, so even a fraction of a percent saved is worth a great deal.

Written as an integer program, it is a set partitioning problem. Let PP be the set of all legal pairings, cpc_p the cost of pairing pp, and aip=1a_{ip}=1 if pairing pp contains leg ii:

min⁡∑p∈Pcp xps.t.∑p∈Paip xp=1    for every leg i,xp∈{0,1}.\min \sum_{p \in P} c_p\, x_p \quad\text{s.t.}\quad \sum_{p \in P} a_{ip}\, x_p = 1 \;\; \text{for every leg } i, \qquad x_p \in \{0,1\}.

The catch is ∣P∣|P|. With a few hundred legs you can still list every pairing; with the schedule of a large carrier the number of legal pairings is far beyond what any computer could store. The model is simple. The trouble is that it has more variables than anyone can write down.

It is a close cousin of exact cover and set cover, and its standard attack combines linear programming with

(route:article/column-generation).

Crew Pairing Lab

Here is a toy airline: four airports, two crew bases (A and B), two days and 23 flight legs. Use the sliders to change the legality rules and the number of legal pairings updates immediately.

<p class="hint">Two crew bases (A and B), two days, 23 flight legs. A <b>pairing</b> is a legal round trip that starts and ends at a base. Choose pairings so that every leg is flown by exactly one crew, at minimum cost. Change the rules and watch the set of legal pairings change.</p>
<div class="rules">
  <label><span>Max duty length <b id="vDuty"></b></span><input id="rDuty" type="range" min="6" max="14" step="1" value="10"></label>
  <label><span>Min connection <b id="vConn"></b></span><input id="rConn" type="range" min="0.5" max="2" step="0.25" value="0.75"></label>
  <label><span>Max flying per duty <b id="vFly"></b></span><input id="rFly" type="range" min="5" max="10" step="1" value="8"></label>
  <div class="chks">
    <label class="chk"><input id="rNight" type="checkbox" checked> Allow overnights</label>
    <label class="chk"><input id="rBaseA" type="checkbox" checked> Base A</label>
    <label class="chk"><input id="rBaseB" type="checkbox" checked> Base B</label>
  </div>
</div>
<div id="count" class="count" aria-live="polite"></div>
<div id="tl" class="tl"></div>
<p class="note">Each bar is a flight leg (clock times; ⁺¹ = next day). Colors show which pairing flies it; grey means not covered yet. Shaded: the night between the two days.</p>
<div class="bar">
  <button id="bGreedy" type="button" class="ghost">Greedy</button>
  <button id="bExact" type="button">Exact (branch and bound)</button>
</div>
<div class="bar">
  <button id="bStep" type="button" class="ghost">Column generation: one iteration</button>
  <button id="bRun" type="button" class="ghost">Run to convergence</button>
  <button id="bReset" type="button" class="ghost">Reset</button>
</div>
<div id="msg" class="msg" aria-live="polite"></div>
<div id="cgbox" hidden>
  <h3>Column generation: the restricted master LP</h3>
  <div id="chart" class="chart"></div>
  <div id="tbl" class="tbl">
    <table>
      <thead><tr><th>Iter.</th><th>LP cost</th><th>Columns</th><th>Best reduced cost</th></tr></thead>
      <tbody id="cgrows"></tbody>
    </table>
  </div>
</div>
<div id="out" class="out"></div>

* { box-sizing: border-box; }
:root { --fg: #1c2530; --muted: #4a5666; --line: #c9d3de; --accent: #1d3557; --on: #ffffff; --idle: #c3ccd6; --night: rgba(60,80,110,.09); --ok: #0f7a3d; --bad: #c0283a; }
@media (prefers-color-scheme: dark) {
  :root { --fg: #e6ebf2; --muted: #a6b2c3; --line: #3a4659; --accent: #8fb4ee; --on: #0d1420; --idle: #4a5668; --night: rgba(160,190,230,.08); --ok: #3ddc84; --bad: #ff6b7d; }
}
body { font-family: system-ui, sans-serif; color: var(--fg); margin: 0; padding: 4px 2px 12px; }
.hint { font-size: .88rem; line-height: 1.45; color: var(--muted); margin: 0 0 8px; }
.rules { display: grid; grid-template-columns: repeat(auto-fit, minmax(150px, 1fr)); gap: 6px 12px; margin: 0 0 6px; }
.rules label { display: flex; flex-direction: column; font-size: .8rem; gap: 2px; }
.rules input[type=range] { width: 100%; accent-color: var(--accent); }
.chks { grid-column: 1 / -1; display: flex; flex-wrap: wrap; gap: 4px 14px; }
.chk { flex-direction: row !important; align-items: center; gap: 5px !important; }
.count { font-weight: 700; font-size: .95rem; margin: 4px 0; }
.tl svg { width: 100%; height: auto; display: block; }
.tl .grid { stroke: var(--line); stroke-width: .6; }
.tl .night { fill: var(--night); }
.tl .ax { font: 7px system-ui, sans-serif; fill: var(--muted); }
.tl .lab { font: 8px ui-monospace, monospace; fill: var(--fg); }
.note { font-size: .75rem; color: var(--muted); margin: 2px 0 8px; }
.bar { display: flex; flex-wrap: wrap; gap: 6px; margin: 0 0 8px; }
button { font: 600 13px system-ui, sans-serif; padding: 6px 11px; border: 1px solid var(--accent); background: var(--accent); color: var(--on); border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--accent); }
button:focus-visible, input:focus-visible { outline: 2px solid var(--accent); outline-offset: 2px; }
.msg { font-size: .88rem; line-height: 1.45; font-weight: 600; margin: 4px 0 8px; min-height: 1.4em; }
h3 { font-size: .95rem; margin: 10px 0 4px; }
.chart svg { width: 100%; height: auto; display: block; }
.chart .ax { font: 8px system-ui, sans-serif; fill: var(--muted); }
.chart .ln { stroke: var(--accent); stroke-width: 1.6; }
.chart .dot { fill: var(--accent); }
.chart .ref { stroke: var(--ok); stroke-width: 1; stroke-dasharray: 4 3; }
.tbl { max-height: 150px; overflow-y: auto; border: 1px solid var(--line); border-radius: 6px; margin: 6px 0; }
table { width: 100%; border-collapse: collapse; font-size: .78rem; font-variant-numeric: tabular-nums; }
th, td { padding: 3px 8px; text-align: right; border-bottom: 1px solid var(--line); }
th { position: sticky; top: 0; background: var(--on); color: var(--muted); font-weight: 600; }
.out ol, .out ul { margin: 4px 0; padding: 0; list-style: none; font-size: .8rem; line-height: 1.5; }
.out li { padding: 2px 0; }
.sw { display: inline-block; width: 10px; height: 10px; border-radius: 3px; margin-right: 6px; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// flight legs: from, to, departure, arrival (hours since day 1 at 00:00)
const LEGS = [["B","A",8,9.5],["A","D",9,10.5],["A","C",9.5,11.5],["A","B",10.75,12.75],["D","C",11.25,13.25],["C","D",12.5,14.5],["B","A",13.75,15.25],["C","A",14.5,16.5],["D","B",15.5,17],["A","B",16,18],["B","A",18.25,19.75],["A","B",32,34],["B","C",33,35],["A","B",34.5,36.5],["B","A",35.25,37.25],["C","D",36,37.5],["B","A",37.5,39.5],["D","A",38.25,40.25],["A","B",38.5,40.5],["A","B",40.25,42.25],["A","B",41,43],["B","A",41.5,43],["B","A",43.5,45.5]];
const NL = LEGS.length;
const REST = 9, MIN_PAY = 3, HOTEL = 2.5, BIG_M = 40;
const hh = (x) => { const d = Math.floor(x / 24), t = x - d * 24, h = Math.floor(t), m = Math.round((t - h) * 60); return String(h).padStart(2, "0") + ":" + String(m).padStart(2, "0") + (d ? "⁺¹" : ""); };
// a duty is a run of legs separated by short connections; a long gap is an overnight rest
function dutiesOf(path) {
  const out = []; let cur = null;
  for (let k = 0; k < path.length; k++) {
    const L = LEGS[path[k]];
    if (cur && L[2] - LEGS[path[k - 1]][3] < REST) { cur.end = L[3]; cur.fly += L[3] - L[2]; }
    else { cur = { start: L[2], end: L[3], fly: L[3] - L[2] }; out.push(cur); }
  }
  return out;
}
function pairingCost(path) {
  const d = dutiesOf(path); let c = 0;
  for (const u of d) c += Math.max(u.fly, 0.4 * (u.end - u.start), MIN_PAY);
  c += HOTEL * (d.length - 1);
  return Math.round(c * 100) / 100;
}
// depth-first enumeration of every legal pairing under the current rules
function enumerate(R, visit) {
  const bases = []; if (R.baseA) bases.push("A"); if (R.baseB) bases.push("B");
  const path = [];
  function go(base, cur, dStart, dFly) {
    const last = LEGS[path[path.length - 1]];
    if (cur === base) visit(path.slice(), base);
    for (let l = 0; l < NL; l++) {
      const L = LEGS[l];
      if (L[0] !== cur) continue;
      const gap = L[2] - last[3];
      if (gap < R.minConn) continue;
      const len = L[3] - L[2];
      if (gap >= REST) {
        if (!R.overnight) continue;
        if (len > R.maxDuty || len > R.maxFly) continue;
        path.push(l); go(base, L[1], L[2], len); path.pop();
      } else {
        if (L[3] - dStart > R.maxDuty || dFly + len > R.maxFly) continue;
        path.push(l); go(base, L[1], dStart, dFly + len); path.pop();
      }
    }
  }
  for (const b of bases) for (let l = 0; l < NL; l++) {
    const L = LEGS[l]; if (L[0] !== b) continue;
    const len = L[3] - L[2]; if (len > R.maxDuty || len > R.maxFly) continue;
    path.push(l); go(b, L[1], L[2], len); path.pop();
  }
}
function buildColumns(R) {
  const cols = [];
  enumerate(R, (p, b) => { cols.push({ legs: p, base: b, cost: pairingCost(p) }); });
  return cols;
}
// exact branch and bound: branch on the leg with fewest options, prune with a per-leg cost bound
function exactSolve(cols, maxNodes) {
  const byLeg = Array.from({ length: NL }, () => []);
  cols.forEach((c, i) => c.legs.forEach((l) => byLeg[l].push(i)));
  byLeg.forEach((a) => a.sort((x, y) => cols[x].cost - cols[y].cost));
  const ratio = new Array(NL).fill(Infinity);
  cols.forEach((c) => c.legs.forEach((l) => { ratio[l] = Math.min(ratio[l], c.cost / c.legs.length); }));
  if (ratio.some((r) => r === Infinity)) return { status: "infeasible", nodes: 0 };
  const cov = new Array(NL).fill(false);
  let best = Infinity, bestSel = null, nodes = 0, cut = false; const sel = [];
  function rec(cost) {
    if (cut) return;
    if (++nodes > maxNodes) { cut = true; return; }
    let lb = 0, pick = -1, pc = Infinity;
    for (let l = 0; l < NL; l++) if (!cov[l]) {
      lb += ratio[l];
      let n = 0; for (const i of byLeg[l]) if (!cols[i].legs.some((x) => cov[x])) n++;
      if (n < pc) { pc = n; pick = l; }
    }
    if (pick < 0) { if (cost < best - 1e-9) { best = cost; bestSel = sel.slice(); } return; }
    if (cost + lb >= best - 1e-9 || pc === 0) return;
    for (const i of byLeg[pick]) {
      const c = cols[i]; if (c.legs.some((x) => cov[x])) continue;
      c.legs.forEach((x) => { cov[x] = true; }); sel.push(i);
      rec(cost + c.cost);
      sel.pop(); c.legs.forEach((x) => { cov[x] = false; });
    }
  }
  rec(0);
  if (bestSel === null) return { status: cut ? "limit" : "infeasible", nodes };
  return { status: cut ? "limit" : "optimal", cost: Math.round(best * 100) / 100, sel: bestSel, nodes };
}
// greedy: always take the cheapest cost per leg that still fits
function greedySolve(cols) {
  const cov = new Array(NL).fill(false), sel = []; let cost = 0;
  for (;;) {
    let bi = -1, br = Infinity;
    cols.forEach((c, i) => { if (c.legs.some((x) => cov[x])) return; const r = c.cost / c.legs.length; if (r < br - 1e-12) { br = r; bi = i; } });
    if (bi < 0) break;
    cols[bi].legs.forEach((x) => { cov[x] = true; }); sel.push(bi); cost += cols[bi].cost;
  }
  const left = []; for (let l = 0; l < NL; l++) if (!cov[l]) left.push(l);
  return { sel, cost: Math.round(cost * 100) / 100, left };
}
// dense simplex for the master LP; penalty columns (cost BIG_M) give a starting basis
function solveLP(cols) {
  const m = NL, n = m + cols.length, W = n + 1;
  const c = new Array(n).fill(0), T = [];
  for (let i = 0; i < m; i++) c[i] = BIG_M;
  cols.forEach((col, j) => { c[m + j] = col.cost; });
  for (let i = 0; i < m; i++) { const row = new Array(W).fill(0); row[i] = 1; row[n] = 1; T.push(row); }
  cols.forEach((col, j) => { for (const l of col.legs) T[l][m + j] = 1; });
  const basis = []; for (let i = 0; i < m; i++) basis.push(i);
  for (let it = 0; it < 20000; it++) {
    let ent = -1;
    for (let j = 0; j < n && ent < 0; j++) {
      let d = c[j]; for (let i = 0; i < m; i++) d -= c[basis[i]] * T[i][j];
      if (d < -1e-9) ent = j;
    }
    if (ent < 0) break;
    let lv = -1, br = Infinity;
    for (let i = 0; i < m; i++) if (T[i][ent] > 1e-9) {
      const r = T[i][n] / T[i][ent];
      if (r < br - 1e-12 || (Math.abs(r - br) <= 1e-12 && basis[i] < basis[lv])) { br = r; lv = i; }
    }
    if (lv < 0) break;
    const pv = T[lv][ent]; for (let j = 0; j < W; j++) T[lv][j] /= pv;
    for (let i = 0; i < m; i++) if (i !== lv && Math.abs(T[i][ent]) > 1e-12) { const f = T[i][ent]; for (let j = 0; j < W; j++) T[i][j] -= f * T[lv][j]; }
    basis[lv] = ent;
  }
  const x = new Array(cols.length).fill(0); let obj = 0, art = 0;
  for (let i = 0; i < m; i++) { obj += c[basis[i]] * T[i][n]; if (basis[i] >= m) x[basis[i] - m] = T[i][n]; else art += T[i][n]; }
  // the dual price of each leg is read from the final basis
  const y = new Array(m).fill(0);
  for (let l = 0; l < m; l++) for (let i = 0; i < m; i++) y[l] += c[basis[i]] * T[i][l];
  return { obj, x, y, art };
}
// pricing: find pairings whose cost is below the sum of their legs' duals
function price(R, y, k, have) {
  const found = [];
  enumerate(R, (p, b) => {
    const cost = pairingCost(p); let rc = cost; for (const l of p) rc -= y[l];
    if (rc < -1e-7 && !have.has(p.join(","))) found.push({ legs: p, base: b, cost, rc });
  });
  found.sort((a, b) => a.rc - b.rc);
  return found.slice(0, k);
}
function colGen(R, k, maxIt) {
  const cols = [], have = new Set(), hist = [];
  for (let it = 1; it <= maxIt; it++) {
    const lp = solveLP(cols);
    const np = price(R, lp.y, k, have);
    hist.push({ it, obj: lp.obj, ncols: cols.length, minrc: np.length ? np[0].rc : 0 });
    if (!np.length) return { hist, cols, lp };
    np.forEach((p) => { have.add(p.legs.join(",")); cols.push(p); });
  }
  return { hist, cols, lp: solveLP(cols) };
}
// user interface
const $ = (id) => document.getElementById(id);
const dark = window.matchMedia && window.matchMedia("(prefers-color-scheme: dark)").matches;
const color = (i) => "hsl(" + ((i * 47) % 360) + " 62% " + (dark ? 62 : 42) + "%)";
const route = (p) => LEGS[p[0]][0] + p.map((l) => "→" + LEGS[l][1]).join("");
const r2 = (v) => (Math.round(v * 100) / 100).toFixed(2);
let R = null, cols = [], exact = null, cg = null;

function readRules() {
  R = { maxDuty: +$("rDuty").value, minConn: +$("rConn").value, maxFly: +$("rFly").value,
        overnight: $("rNight").checked, baseA: $("rBaseA").checked, baseB: $("rBaseB").checked };
  $("vDuty").textContent = R.maxDuty + " h";
  $("vConn").textContent = R.minConn + " h";
  $("vFly").textContent = R.maxFly + " h";
}
function resetState() {
  readRules();
  cols = buildColumns(R);
  exact = null;
  cg = { cols: [], have: new Set(), hist: [], done: false, added: [], lp: null };
  const nb = (R.baseA ? 1 : 0) + (R.baseB ? 1 : 0);
  $("count").textContent = fmt("%n% legal pairings from %b% base(s)", { n: cols.length, b: nb });
  $("out").innerHTML = "";
  $("msg").textContent = "";
  $("cgbox").hidden = true;
  drawTimeline([]);
}
function getExact() {
  if (!exact) exact = exactSolve(cols, 1500000);
  return exact;
}
function drawTimeline(sel) {
  const asg = new Array(NL).fill(-1);
  sel.forEach((ci, k) => cols[ci].legs.forEach((l) => { asg[l] = k; }));
  const X0 = 44, X1 = 352, T0 = 6, T1 = 46, RH = 11, H = NL * RH + 18;
  const sx = (t) => X0 + (t - T0) * (X1 - X0) / (T1 - T0);
  let s = '<svg viewBox="0 0 360 ' + H + '" role="img" aria-label="Timeline of flight legs colored by crew pairing">';
  for (const t of [8, 12, 16, 20, 32, 36, 40, 44]) {
    s += '<line x1="' + sx(t) + '" x2="' + sx(t) + '" y1="12" y2="' + (H - 2) + '" class="grid"/><text x="' + sx(t) + '" y="9" class="ax" text-anchor="middle">' + hh(t) + '</text>';
  }
  s += '<rect x="' + sx(21) + '" y="12" width="' + (sx(31) - sx(21)) + '" height="' + (H - 14) + '" class="night"/>';
  LEGS.forEach((L, i) => {
    const y = 14 + i * RH;
    const fill = asg[i] >= 0 ? color(asg[i]) : "var(--idle)";
    s += '<text x="2" y="' + (y + 7.5) + '" class="lab">' + L[0] + "→" + L[1] + '</text>';
    s += '<rect x="' + sx(L[2]) + '" y="' + y + '" width="' + (sx(L[3]) - sx(L[2])) + '" height="8" rx="2" fill="' + fill + '"/>';
  });
  $("tl").innerHTML = s + "</svg>";
}
function listSolution(sel, weights) {
  let h = "";
  sel.forEach((ci, k) => {
    const c = cols[ci], d = dutiesOf(c.legs);
    const w = weights ? '<b>x=' + r2(weights[k]) + '</b> ' : "";
    h += '<li><i class="sw" style="background:' + color(k) + '"></i>' + w + fmt("%route%  %t1%–%t2%  ·  cost %c%  ·  duties: %d%", { route: route(c.legs), t1: hh(LEGS[c.legs[0]][2]), t2: hh(LEGS[c.legs[c.legs.length - 1]][3]), c: r2(c.cost), d: d.length }) + '</li>';
  });
  $("out").innerHTML = "<ol>" + h + "</ol>";
}
function doGreedy() {
  const g = greedySolve(cols);
  drawTimeline(g.sel); listSolution(g.sel);
  if (g.left.length) $("msg").textContent = fmt("Greedy picked %k% pairings (cost %c%) and got stuck: %m% legs can no longer be covered without overlap: %legs%.", { k: g.sel.length, c: r2(g.cost), m: g.left.length, legs: g.left.map((l) => LEGS[l][0] + "→" + LEGS[l][1] + " " + hh(LEGS[l][2])).join(", ") });
  else {
    const e = getExact();
    $("msg").textContent = fmt("Greedy covered every leg with %k% pairings, cost %c%. The exact optimum is %o%.", { k: g.sel.length, c: r2(g.cost), o: e.cost === undefined ? "?" : r2(e.cost) });
  }
}
function doExact() {
  const t0 = performance.now();
  exact = null;
  const e = getExact();
  const ms = Math.round(performance.now() - t0);
  if (e.status === "infeasible") { drawTimeline([]); $("out").innerHTML = ""; $("msg").textContent = fmt("No exact partition exists: with these rules the %n% legal pairings cannot cover every leg exactly once. Relax a rule.", { n: cols.length }); return; }
  drawTimeline(e.sel); listSolution(e.sel);
  $("msg").textContent = fmt(e.status === "optimal" ? "Optimal: %k% pairings, cost %c%. Branch and bound explored %nodes% nodes over %n% pairings (%ms% ms)." : "Node limit reached. Best solution found: %k% pairings, cost %c% (not proven optimal).", { k: e.sel.length, c: r2(e.cost), nodes: e.nodes, n: cols.length, ms });
}
function drawChart() {
  const H = cg.hist; if (!H.length) return;
  const W = 340, HT = 90, L0 = 34, ymin = Math.log(Math.max(1, Math.min(...H.map((h) => h.obj)) * 0.8)), ymax = Math.log(Math.max(...H.map((h) => h.obj)) * 1.1);
  const sx = (i) => L0 + (H.length === 1 ? 0 : i * (W - L0 - 6) / (H.length - 1));
  const sy = (v) => 8 + (HT - 16) * (1 - (Math.log(Math.max(v, 1)) - ymin) / Math.max(1e-9, ymax - ymin));
  let s = '<svg viewBox="0 0 ' + W + " " + HT + '" role="img" aria-label="LP objective value per column generation iteration, log scale">';
  s += '<text x="2" y="14" class="ax">' + Math.round(Math.max(...H.map((h) => h.obj))) + '</text><text x="2" y="' + (HT - 4) + '" class="ax">' + Math.round(Math.min(...H.map((h) => h.obj))) + '</text>';
  if (exact && exact.cost !== undefined) s += '<line x1="' + L0 + '" x2="' + W + '" y1="' + sy(exact.cost) + '" y2="' + sy(exact.cost) + '" class="ref"/>';
  s += '<polyline fill="none" class="ln" points="' + H.map((h, i) => sx(i) + "," + sy(h.obj)).join(" ") + '"/>';
  H.forEach((h, i) => { s += '<circle cx="' + sx(i) + '" cy="' + sy(h.obj) + '" r="2.4" class="dot"/>'; });
  $("chart").innerHTML = s + "</svg>";
}
function renderCG() {
  $("cgbox").hidden = false;
  drawChart();
  $("cgrows").innerHTML = cg.hist.map((h) => "<tr><td>" + h.it + "</td><td>" + r2(h.obj) + "</td><td>" + h.ncols + "</td><td>" + (h.minrc < -1e-7 ? r2(h.minrc) : "≥ 0") + "</td></tr>").join("");
  const box = $("tbl"); box.scrollTop = box.scrollHeight;
  if (!cg.done) {
    $("out").innerHTML = "<ul>" + cg.added.map((p) => "<li>" + fmt("New column %route%: cost %c% − duals %y% = reduced cost %rc%", { route: route(p.legs), c: r2(p.cost), y: r2(p.cost - p.rc), rc: r2(p.rc) }) + "</li>").join("") + "</ul>";
    $("msg").textContent = fmt("Iteration %it%: the LP costs %obj% using %n% of the %tot% legal pairings. Press again.", { it: cg.hist.length, obj: r2(cg.lp.obj), n: cg.cols.length, tot: cols.length });
    return;
  }
  const lp = cg.lp;
  if (lp.art > 1e-6) { $("out").innerHTML = ""; $("msg").textContent = fmt("After %it% iterations the master still needs penalty columns: no set of legal pairings covers every leg. Relax a rule.", { it: cg.hist.length }); drawTimeline([]); return; }
  const idx = []; lp.x.forEach((v, i) => { if (v > 1e-6) idx.push(i); });
  const frac = idx.some((i) => Math.abs(lp.x[i] - 1) > 1e-6);
  const e = getExact();
  const ig = exactSolve(cg.cols, 1500000);
  const base = fmt("Converged after %it% iterations: no pairing has negative reduced cost, so the LP optimum is %obj%, reached with only %n% of the %tot% pairings.", { it: cg.hist.length, obj: r2(lp.obj), n: cg.cols.length, tot: cols.length });
  const mid = frac ? fmt("The LP solution is fractional (%k% columns with weights x).", { k: idx.length }) : "The LP solution happens to be integral.";
  const own = ig.status === "infeasible" ? "" : fmt("Best integer solution from the generated columns alone: %c% (true optimum with all pairings: %o%).", { c: r2(ig.cost), o: e.cost === undefined ? "?" : r2(e.cost) });
  $("msg").textContent = base + " " + mid + " " + own;
  drawChart();
  listLP(idx, lp);
  if (!frac) { const tmp = cols; cols = cg.cols; drawTimeline(idx); cols = tmp; } else drawTimeline([]);
}
function listLP(idx, lp) {
  const tmp = cols; cols = cg.cols; listSolution(idx, idx.map((i) => lp.x[i])); cols = tmp;
}
function cgStep() {
  if (cg.done) return;
  const lp = solveLP(cg.cols);
  const np = price(R, lp.y, 3, cg.have);
  cg.hist.push({ it: cg.hist.length + 1, obj: lp.obj, ncols: cg.cols.length, minrc: np.length ? np[0].rc : 0 });
  cg.lp = lp; cg.added = np;
  if (!np.length) cg.done = true;
  else np.forEach((p) => { cg.have.add(p.legs.join(",")); cg.cols.push(p); });
  renderCG();
}
function cgRun() {
  let guard = 0;
  while (!cg.done && guard++ < 200) cgStep();
}
["rDuty", "rConn", "rFly", "rNight", "rBaseA", "rBaseB"].forEach((id) => $(id).addEventListener("input", resetState));
$("bGreedy").addEventListener("click", doGreedy);
$("bExact").addEventListener("click", doExact);
$("bStep").addEventListener("click", cgStep);
$("bRun").addEventListener("click", cgRun);
$("bReset").addEventListener("click", resetState);
resetState();
Result
Console

Try these experiments:

  • Greedy. Repeatedly take the pairing with the lowest cost per leg that still fits. With the default rules it paints itself into a corner: a few legs end up that no remaining pairing can fly without overlapping.
  • Exact. Branch and bound branches on the leg with the fewest candidate pairings and prunes with a cost bound. It proves an optimum and reports how many nodes it needed.
  • Column generation. Instead of listing every pairing, start with none (only expensive penalty columns), solve the LP, read the dual price of each leg, and ask the pricing step for pairings whose cost is lower than the sum of the duals of the legs they cover. Each iteration adds the best ones. Watch the LP cost fall and the master use only a fraction of all legal pairings.
  • Break it. Switch overnights off, or tighten the duty limit: at some point no exact partition exists, and the demo says so.

The Real Complexity

Crew pairing stacks three separate difficulties.

1. The partitioning itself is NP-hard. Set partitioning generalizes exact cover, one of Karp's original 21 NP-complete problems (1972). Deciding whether any feasible partition exists is already NP-complete in general, which is why the demo can end with "no exact partition exists".

2. There are exponentially many columns. If each leg can be followed by dd others, the number of chains of up to kk legs grows like d kd^{\,k}. With multi-day pairings of up to four or five duties, ∣P∣|P| reaches the millions or billions on real networks. Even writing down the constraint matrix is impossible. In our toy: 23 legs give just 149 pairings under the default rules, but the count grows fast as the rules loosen.

3. Pricing is a constrained shortest path. Column generation, introduced by Gilmore and Gomory in 1961 for the cutting stock problem, keeps a small restricted master of mm rows and a subset of columns. After solving the master LP with duals πi\pi_i, a pairing pp can improve the solution only if its reduced cost is negative:

cˉp=cp−∑i∈pπi<0.\bar c_p = c_p - \sum_{i \in p} \pi_i < 0.

Finding the most negative cˉp\bar c_p is a resource-constrained shortest path over a graph whose nodes are legs. Resources are duty time, flying time and elapsed days, and the cost of a duty (for example max⁡(flying, 0.4⋅elapsed, minimum guarantee)\max(\text{flying},\ 0.4\cdot\text{elapsed},\ \text{minimum guarantee})) is not additive over legs. This problem is NP-hard in general, but it is only weakly NP-hard: label-setting dynamic programming with dominance rules solves it in pseudo-polynomial time in the resource ranges. Real systems run it with some form of heuristic acceleration.

master <- empty set of pairings (plus penalty columns)
repeat
    solve LP(master)   ->  duals pi
    P* <- pairings p with  c_p - sum(pi_i for i in p) < 0   (pricing)
    if P* is empty: stop            # LP optimum over ALL pairings
    add the best pairings of P* to master

When the loop stops, the LP optimum over all ∣P∣|P| pairings has been found, usually after tens or hundreds of iterations, and no theoretical polynomial bound on the iteration count is known for this scheme. (In the demo with its default rules: 17 iterations, 45 of the 149 pairings.)

From LP to integers. The LP bound is usually very tight for crew pairing: the LP optimum typically lies very close to the best integer cost. The demo's default instance is a small example: the LP optimum is 48.5548.55 and the best integer solution costs 4949, a gap under 1%1\%. To close it, the column generation is embedded in a branch-and-bound tree where every node re-solves the LP with new columns, a scheme named branch-and-price (Barnhart, Johnson, Nemhauser, Savelsbergh and Vance, Operations Research, 1998). Branching on single pairings is a poor idea, because the pricing step would simply regenerate the excluded column. Instead one branches on structure, such as whether leg jj immediately follows leg ii in a pairing (the follow-on branching described in that literature), a rule the pricing network can respect.

Space and time. The demo stores all columns explicitly (O(∣P∣⋅L)O(|P|\cdot L) memory for LL legs), which is exactly what real systems avoid by generating only the columns they need.

Where It Matters

  • Airlines. Crew cost is usually cited as the second-largest operating expense after fuel. Optimization of pairings has been a production tool for decades: American Airlines' pairing optimizer, described by Anbil, Gelman, Patty and Tanga (Interfaces, 1991), reported annual savings above 20 million US dollars, and the system was sold to other airlines.
  • Crew rostering, the next stage. Pairings are anonymous. The follow-on rostering problem assigns them to named individuals, honoring vacations, qualifications, rest rules and fairness over a month. It resembles nurse rostering and is again solved with column generation over individual work schedules.
  • Recovery. When storms or breakdowns disrupt a day, planners must re-optimize the remaining pairings in minutes rather than hours, with strong penalties for changing the plan.
  • Rail, bus and ship crews. The same partitioning structure appears wherever a fixed timetable must be covered by legally constrained shifts.
  • Beyond transport. Vehicle routing, cutting stock and many other integer programs share the pattern "choose columns that partition the rows", which is why branch-and-price became a general-purpose technique.

Conclusion

Crew pairing is set partitioning with a twist: the variables are too numerous to list. The solution is to optimize over a set you never write down. Solve a small LP, read the dual prices of the flights, ask a shortest-path subroutine for the one pairing that would help most, add it, and repeat until none exists. Then branch on structure, not on columns, to reach integers.

It is a good reminder that the hardness of a problem can live in the size of the model as much as in its logic, and that the right decomposition (Dantzig-Wolfe, LP duality, branch-and-bound) can turn an impossible list into a loop of small, solvable steps.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/crew-pairing/Content licensed under CC BY-NC 4.0.