Introduction

Imagine a linear program with millions of variables but a special structure: most constraints involve only a small, independent block of variables, while a handful of linking constraints tie everything together. Solving it directly drowns any solver in columns.

In 1960, George Dantzig and Philip Wolfe found an elegant escape. Their decomposition principle rewrites the monster LP as a master problem over convex combinations of block-feasible points, then iteratively asks each block: "Can you produce a point that would improve the master?" Those points are columns generated on demand — you never enumerate the full variable space.

The trick is the reduced cost: a candidate column is worth adding only when its reduced cost is negative (for minimization). Computing that reduced cost is exactly the subproblem. If every subproblem returns a non-negative reduced cost, the current master solution is already LP-optimal — no further columns can help.

The algorithm was published in Operations Research vol. 8 (1960) and has been the engine behind airline crew scheduling, railway planning, and integer-programming branch-and-price ever since.

Try It: Column Generation

The demo below simulates one decomposition cycle. A master problem holds a restricted set of columns and asks each subproblem for an improving column by checking reduced costs. Click Run one iteration to see the subproblem price out a new column and add it, or click Run to optimality to keep going until no profitable column remains.

<!-- Dantzig-Wolfe column generation demo — master problem panel and subproblem panel -->
<div class="dw-wrap">
  <div class="panel master-panel">
    <h3>Master Problem</h3>
    <div class="info-line">Objective: <span id="master-obj">—</span></div>
    <div class="info-line">Duals: <span id="master-duals">—</span></div>
    <div class="col-list-label">Active columns:</div>
    <div id="col-list" class="col-list"></div>
  </div>
  <div class="arrow-col">
    <div class="arrow-block">
      <div class="arrow-label">duals →</div>
      <div class="arrow">&#8594;</div>
    </div>
    <div class="arrow-block">
      <div class="arrow-label">← new column</div>
      <div class="arrow rev">&#8592;</div>
    </div>
  </div>
  <div class="panel sub-panel">
    <h3>Subproblem (Pricing)</h3>
    <div class="info-line">Best reduced cost: <span id="sub-rc">—</span></div>
    <div class="info-line">New column: <span id="sub-col">—</span></div>
    <div class="status-bar" id="status-bar">Press ’Run one iteration’ to begin column generation.</div>
  </div>
</div>
<div class="btns">
  <button id="btn-step" type="button">Run one iteration</button>
  <button id="btn-run" type="button">Run to optimality</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="iter-line" id="iter-line">Iteration: <span id="iter-count">0</span></div>

/* Layout for the two-panel master/subproblem visualization */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; font-size: 14px; color: #222; margin: 0; padding: 4px; }
.dw-wrap { display: flex; align-items: stretch; gap: 0; margin-bottom: .6rem; }
.panel { flex: 1; border: 1.5px solid #cdd9e3; border-radius: 10px; padding: .65rem .8rem; background: #f5f8fb; min-width: 0; }
.panel h3 { margin: 0 0 .4rem; font-size: .9rem; color: #1d3557; }
.info-line { font-size: .82rem; color: #444; margin-bottom: .25rem; }
.info-line span { font-weight: 700; color: #1d3557; }
.col-list-label { font-size: .78rem; color: #666; margin-top: .35rem; margin-bottom: .2rem; }
.col-list { display: flex; flex-wrap: wrap; gap: .25rem; min-height: 1.6rem; }
.col-tag { font-size: .75rem; background: #dde8f0; border: 1px solid #b8cfe0; border-radius: 5px;
           padding: .15rem .35rem; font-family: ui-monospace, monospace; transition: background .3s; }
.col-tag.new { background: #c3e8d0; border-color: #5cb37b; }
.arrow-col { display: flex; flex-direction: column; justify-content: center; align-items: center;
             gap: .6rem; padding: 0 .4rem; }
.arrow-block { text-align: center; }
.arrow-label { font-size: .68rem; color: #888; margin-bottom: .05rem; }
.arrow { font-size: 1.3rem; color: #1d3557; }
.arrow.rev { color: #0a7d33; }
.status-bar { margin-top: .4rem; font-size: .82rem; font-weight: 600; min-height: 2.2rem;
              border-radius: 7px; padding: .3rem .5rem; background: #e8eef3; color: #333; }
.status-bar.ok { background: #d4f0df; color: #0a7d33; }
.status-bar.done { background: #fff3cd; color: #856404; }
.status-bar.bad { background: #fde8e8; color: #c92f3c; }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.iter-line { font-size: .8rem; color: #666; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Dantzig-Wolfe column generation — simplified two-block LP illustration
// Model: two independent blocks, each a small LP, linked by two capacity constraints.
// The master prices extreme points; subproblems find the most negative reduced cost.

// Master problem (Dantzig-Wolfe reformulation):
// minimize  c^T x  subject to  Ax = b, x >= 0 (convex combination of block extreme points)
// Two blocks, each with four extreme points:
// Block 1 extreme points (x1,x2): (0,0),(4,0),(3,2),(0,3)
// Block 2 extreme points (x3,x4): (0,0),(5,0),(4,2),(0,4)
// Linking constraints:  x1+x3 <= 6,  x2+x4 <= 5
// Objective: minimize -(3*x1+2*x2) - (2*x3+4*x4)  [i.e. maximize revenue]

// Extreme points of each block’s feasible region (LP vertices)
const BLOCK1 = [
  [0,0], [4,0], [3,2], [0,3]
];
const BLOCK2 = [
  [0,0], [5,0], [4,2], [0,4]
];

// Objective coefficients for each block
const C1 = [3,2]; // block 1 revenue per unit of (x1,x2)
const C2 = [2,4]; // block 2 revenue per unit of (x3,x4)
// Right-hand side of linking constraints
const B = [6, 5]; // capacity for resource 1 and resource 2

// Algorithm state
let columns = []; // columns added to the master so far (as human-readable labels)
let duals = [0, 0]; // dual prices for the two linking constraints, start at zero
let masterObj = 0;
let iteration = 0;
let done = false;

function dot(a, b) { return a.reduce((s,v,i)=>s+v*b[i], 0); }

// Compute reduced cost of a candidate column for each block
// reduced cost of a block point p using dual vector pi:
// rc = -(c^T p) + pi^T A_block p
// where A_block selects the linking-constraint coefficients for this block
function reducedCost1(p) {
  // Block 1: columns are [x1,x2], linking rows are [x1, x2] with RHS [6,5]
  return -(C1[0]*p[0] + C1[1]*p[1]) + duals[0]*p[0] + duals[1]*p[1];
}
function reducedCost2(p) {
  // Block 2: columns are [x3,x4], linking rows are [x3, x4] with RHS [6,5]
  return -(C2[0]*p[0] + C2[1]*p[1]) + duals[0]*p[0] + duals[1]*p[1];
}

// Simplified master LP solver (subgradient dual update for illustration)
// We simulate a simplified master: we track selected extreme points and solve
// the master LP by greedy dual update (for illustration).
function solveMaster() {
  // Greedy: pick best extreme point per block under current duals
  // Pick the best column from each block by objective contribution minus dual penalty.
  // For illustration we use a simple greedy: find point in each block maximizing
  // net objective (c - dual*A) contribution, then compute the resulting obj and duals.
  let best1 = null, best1Score = -Infinity;
  for (const p of BLOCK1) {
    const score = C1[0]*p[0]+C1[1]*p[1] - duals[0]*p[0] - duals[1]*p[1];
    if (score > best1Score) { best1Score = score; best1 = p; }
  }
  let best2 = null, best2Score = -Infinity;
  for (const p of BLOCK2) {
    const score = C2[0]*p[0]+C2[1]*p[1] - duals[0]*p[0] - duals[1]*p[1];
    if (score > best2Score) { best2Score = score; best2 = p; }
  }
  // Subgradient dual update — move duals toward feasibility of linking constraints
  // Update duals: dual[i] = max(0, prev + step*(usage - rhs)) — simple subgradient step
  const stepSize = 0.4 / (iteration + 1);
  const usage0 = (best1 ? best1[0] : 0) + (best2 ? best2[0] : 0);
  const usage1 = (best1 ? best1[1] : 0) + (best2 ? best2[1] : 0);
  duals[0] = Math.max(0, duals[0] + stepSize*(usage0 - B[0]));
  duals[1] = Math.max(0, duals[1] + stepSize*(usage1 - B[1]));
  // Compute primal objective value from selected extreme points
  masterObj = (best1 ? C1[0]*best1[0]+C1[1]*best1[1] : 0)
            + (best2 ? C2[0]*best2[0]+C2[1]*best2[1] : 0);
  return { best1, best2 };
}

// Pricing step: find the extreme point with most negative reduced cost in each block
function priceSubproblems() {
  let minRc1 = Infinity, bestP1 = null;
  for (const p of BLOCK1) {
    const rc = reducedCost1(p);
    if (rc < minRc1) { minRc1 = rc; bestP1 = p; }
  }
  let minRc2 = Infinity, bestP2 = null;
  for (const p of BLOCK2) {
    const rc = reducedCost2(p);
    if (rc < minRc2) { minRc2 = rc; bestP2 = p; }
  }
  return { minRc1, bestP1, minRc2, bestP2 };
}

function fmt(n) { return n.toFixed(3); }
function colTag(label, isNew) {
  const el = document.createElement('span');
  el.className = 'col-tag' + (isNew ? ' new' : '');
  el.textContent = label;
  return el;
}

function render(newCols) {
  document.getElementById('master-obj').textContent = fmt(masterObj);
  document.getElementById('master-duals').textContent =
    'π₁=' + fmt(duals[0]) + ', π₂=' + fmt(duals[1]);
  const list = document.getElementById('col-list');
  list.innerHTML = '';
  columns.forEach((c, i) => {
    const isNew = newCols && i >= columns.length - newCols;
    list.appendChild(colTag(c, isNew));
  });
  document.getElementById('iter-count').textContent = iteration;
}

function setStatus(msg, cls) {
  const el = document.getElementById('status-bar');
  el.textContent = msg;
  el.className = 'status-bar ' + (cls||'');
}

function step() {
  if (done) return;
  iteration++;

  // Step 1: price subproblems with current duals to find best extreme points
  // Step 1: price subproblems with current duals to find best extreme points
  const { minRc1, bestP1, minRc2, bestP2 } = priceSubproblems();
  const overallMinRc = Math.min(minRc1, minRc2);
  document.getElementById('sub-rc').textContent = fmt(overallMinRc);

  // Step 2: add any genuinely new columns with negative reduced cost
  // Step 2: add any genuinely new columns with negative reduced cost
  let addedCount = 0;
  let newColLabel = '';
  if (minRc1 < -0.001 && bestP1) {
    const lbl = 'B1(' + bestP1[0] + ',' + bestP1[1] + ')';
    if (!columns.includes(lbl)) { columns.push(lbl); addedCount++; newColLabel = lbl; }
  }
  if (minRc2 < -0.001 && bestP2) {
    const lbl = 'B2(' + bestP2[0] + ',' + bestP2[1] + ')';
    if (!columns.includes(lbl)) { columns.push(lbl); addedCount++; newColLabel += (newColLabel?' & ':'') + lbl; }
  }
  document.getElementById('sub-col').textContent = newColLabel || '—';

  // Optimality: no new column has negative reduced cost (all best extreme points already in master)
  // Optimality: no new column has negative reduced cost (all best extreme points already in master)
  if (addedCount === 0) {
    done = true;
    // Run a final master solve to update displayed objective
    solveMaster();
    render(0);
    setStatus('Optimality reached — no column has negative reduced cost.', 'done');
    document.getElementById('btn-step').disabled = true;
    document.getElementById('btn-run').disabled = true;
    return;
  }

  // Step 3: re-solve master with the new columns (updates masterObj and duals)
  // Step 3: re-solve master with the new columns (updates masterObj and duals)
  solveMaster();
  render(addedCount);
  setStatus(i18nFmt('Added column %newColLabel% to the master.', { newColLabel: newColLabel }), 'ok');
}

function runAll() {
  // Safety limit to avoid infinite loop in edge cases
  if (done) return;
  const MAX = 20;
  while (!done && iteration < MAX) step();
}

function reset() {
  columns = [];
  duals = [0, 0];
  masterObj = 0;
  iteration = 0;
  done = false;
  document.getElementById('master-obj').textContent = '—';
  document.getElementById('master-duals').textContent = '—';
  document.getElementById('sub-rc').textContent = '—';
  document.getElementById('sub-col').textContent = '—';
  document.getElementById('col-list').innerHTML = '';
  document.getElementById('iter-count').textContent = '0';
  document.getElementById('btn-step').disabled = false;
  document.getElementById('btn-run').disabled = false;
  setStatus('Press ’Run one iteration’ to begin column generation.', '');
}

document.getElementById('btn-step').addEventListener('click', step);
document.getElementById('btn-run').addEventListener('click', runAll);
document.getElementById('btn-reset').addEventListener('click', reset);
Result
Console

Notice the pattern: each iteration the master gets a tighter LP bound, and the subproblem's best reduced cost creeps toward zero. When it reaches zero (or becomes positive), you have proven the current master solution is LP-optimal — without ever listing all possible columns.

The Real Complexity

Dantzig-Wolfe decomposition solves the LP relaxation exactly — but how fast?

  • Each iteration solves a restricted master LP and one subproblem (a min-cost optimization over a block's feasible region). If the subproblem is itself a linear program or a network flow, it is fast.
  • Convergence to LP optimality is guaranteed for bounded, feasible problems. In theory the number of column-generation iterations can be exponential; in practice for well-structured problems it is typically tens to a few hundred.
  • Degeneracy is the main practical hazard: cycling or slow progress when multiple bases share the same LP value. Stabilization techniques (e.g., proximal terms, boxstep) are standard remedies.
  • Integrality gap: for integer programs (e.g., crew scheduling), the LP bound from the master is often much tighter than the standard LP relaxation — precisely because the master prices over integer-feasible extreme points of each block. This is the power of branch-and-price.
  • Benders decomposition is the LP dual of Dantzig-Wolfe: instead of generating columns for the master, Benders generates cuts (rows). Both split a hard problem; which is better depends on structure.

The status of Dantzig-Wolfe is solved: the algorithm is correct and complete for LP relaxations. The open questions live in the integer-programming layer on top — how to branch efficiently, how to stabilize, and whether the pricing subproblem itself remains easy as the model grows.

Where It Matters

Block-structured LPs appear everywhere in operations research and beyond:

  • Airline crew scheduling: millions of feasible pairings form the columns; the master selects a minimum-cost cover; subproblems are shortest-path problems on a time-space network.
  • Cutting-stock: each cutting pattern is a column; the subproblem is a knapsack that finds the pattern with the best reduced cost.
  • Vehicle routing (VRP): each route through a subset of customers is a column; the master covers every customer; subproblems are shortest Hamiltonian paths with capacity.
  • Railway and bus timetabling: blocks correspond to train units or bus depots; the master enforces fleet balance constraints.
  • Integer programming via branch-and-price: add branching on top of column generation to solve large MIPs whose LP relaxations are tight through decomposition.

Whenever a problem has a block structure — many nearly independent groups of variables tied by a few global constraints — Dantzig-Wolfe is the standard first tool to reach for. It turns problems that would take years of solver time into problems solved in minutes.

Conclusion

Dantzig-Wolfe decomposition reveals a beautiful duality between problem size and problem structure: a linear program with millions of columns becomes tractable the moment you recognize it as a collection of independent blocks tied by a few linking constraints.

The master asks, the subproblems answer. Each improving column tightens the bound. When no subproblem can find a negative reduced cost, the algorithm stops — not because it gave up, but because it has proven optimality. No better solution exists.

Sixty-five years after the original paper, column generation and branch-and-price remain the method of choice for the largest scheduling and routing problems in the world. The insight is timeless: you rarely need all the columns — just the right ones.

Share this article

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

Comments

Loading comments...

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