Dantzig-Wolfe Decomposition

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.

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.

<!-- {{c_html_intro}} -->
<div class="dw-wrap">
  <div class="panel master-panel">
    <h3>{{lbl_master}}</h3>
    <div class="info-line">{{lbl_obj}} <span id="master-obj">—</span></div>
    <div class="info-line">{{lbl_duals}} <span id="master-duals">—</span></div>
    <div class="col-list-label">{{lbl_active_cols}}</div>
    <div id="col-list" class="col-list"></div>
  </div>
  <div class="arrow-col">
    <div class="arrow-block">
      <div class="arrow-label">{{lbl_duals_flow}}</div>
      <div class="arrow">&#8594;</div>
    </div>
    <div class="arrow-block">
      <div class="arrow-label">{{lbl_col_flow}}</div>
      <div class="arrow rev">&#8592;</div>
    </div>
  </div>
  <div class="panel sub-panel">
    <h3>{{lbl_sub}}</h3>
    <div class="info-line">{{lbl_rc}} <span id="sub-rc">—</span></div>
    <div class="info-line">{{lbl_best_col}} <span id="sub-col">—</span></div>
    <div class="status-bar" id="status-bar">{{msg_start}}</div>
  </div>
</div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="iter-line" id="iter-line">{{lbl_iter}} <span id="iter-count">0</span></div>

/* {{c_css_layout}} */
* { 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; }

// Code not found

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.

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.

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.

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.