Introduction

A linear program can have more variables than atoms in the observable universe. Listing them all — let alone handing them to a solver — is hopeless. Yet some of the most important optimization problems in the world (airline crew schedules, truck routes, cutting patterns) have exactly this shape.

Column generation is the trick that makes them tractable. The idea is brutally simple: instead of writing down every variable, you start with a tiny handful, solve the small problem optimally, and then ask a clever question — is there any variable I left out that could still improve the solution? If yes, add it and re-solve. If no, you are done; the small solution is already globally optimal.

The "clever question" is itself an optimization problem called the pricing subproblem. Its output is a single new column (variable) that, if it exists, has the best chance of reducing cost. The loop — solve the restricted LP, price a new column, add it, repeat — is the column generation algorithm, introduced by Gilmore and Gomory in 1961 for cutting-stock problems and later unified by Dantzig and Wolfe's decomposition principle.

The payoff is dramatic: problems with trillions of variables are solved with a few hundred columns in practice.

Watch It Work

Below is a small set-cover LP: we have 6 items (1–6) and a universe of possible subsets, each with a cost. We want to cover every item at minimum total cost. The LP has dozens of possible columns (subsets), but column generation starts with just a few and adds the most profitable one at each step.

<div class="cg-wrap">
  <div class="cg-top">
    <div class="cg-left">
      <div class="legend"><strong>Items to cover:</strong><span id="items-display"></span></div>
      <div class="col-list-wrap">
        <div class="col-list-label">Active columns (restricted LP):</div>
        <div id="active-cols" class="col-list"></div>
      </div>
      <div class="col-list-wrap">
        <div class="col-list-label">Pool (not yet added):</div>
        <div id="pool-cols" class="col-list pool"></div>
      </div>
    </div>
    <div class="cg-right">
      <div class="result-box">
        <div class="rb-title">LP solution</div>
        <div id="rb-body">Press "Next iteration" to begin.</div>
      </div>
      <div class="pricing-box" id="pricing-box" style="display:none">
        <div class="pb-title">Pricing step</div>
        <div id="pb-body"></div>
      </div>
    </div>
  </div>
  <div class="btns">
    <button id="btn-next" type="button">Next iteration</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
  <div id="log" class="log"></div>
</div>

*{box-sizing:border-box;}
body{font-family:system-ui,sans-serif;color:#1a2233;margin:0;font-size:14px;}
.cg-wrap{padding:4px 0;}
.cg-top{display:flex;gap:14px;flex-wrap:wrap;}
.cg-left,.cg-right{flex:1;min-width:190px;}
.legend{margin-bottom:8px;font-size:13px;}
#items-display{display:inline-flex;gap:5px;flex-wrap:wrap;margin-left:6px;}
.item-chip{width:26px;height:26px;border-radius:50%;display:inline-flex;align-items:center;
           justify-content:center;font:700 12px monospace;border:2px solid #1d3557;color:#1d3557;}
.item-chip.covered{background:#1d3557;color:#fff;}
.col-list-wrap{margin-bottom:9px;}
.col-list-label{font-size:11px;font-weight:700;color:#666;text-transform:uppercase;letter-spacing:.04em;margin-bottom:5px;}
.col-list{display:flex;flex-wrap:wrap;gap:5px;}
.col-chip{border-radius:6px;padding:4px 9px;font:600 12px monospace;cursor:default;
          background:#e8eef3;border:1.5px solid #b0bec5;color:#1a2233;display:flex;align-items:center;gap:5px;}
.col-chip .cc-sub{font-size:10px;color:#546e7a;}
.col-chip.entering{background:#fff3cd;border-color:#f59e0b;animation:pulse .5s ease 2;}
.col-chip.in-basis{background:#d1fae5;border-color:#10b981;color:#064e3b;}
.col-chip.dropped{background:#fee2e2;border-color:#ef4444;color:#7f1d1d;text-decoration:line-through;}
@keyframes pulse{0%,100%{transform:scale(1);}50%{transform:scale(1.1);}}
.pool .col-chip{background:#f5f5f5;border-color:#d1d5db;color:#9ca3af;}
.result-box,.pricing-box{border-radius:8px;padding:10px 13px;margin-bottom:10px;font-size:13px;line-height:1.7;}
.result-box{background:#eff6ff;border:1.5px solid #93c5fd;}
.pricing-box{background:#fffbeb;border:1.5px solid #fcd34d;}
.rb-title,.pb-title{font-weight:700;font-size:11px;text-transform:uppercase;letter-spacing:.05em;margin-bottom:4px;}
.rb-title{color:#1e40af;}.pb-title{color:#b45309;}
.row{margin:1px 0;}
.hi{font-weight:700;color:#1e40af;}
.hi-neg{font-weight:700;color:#b91c1c;}
.hi-ok{font-weight:700;color:#065f46;}
.btns{display:flex;gap:8px;margin:10px 0;}
button{font:600 13px system-ui;padding:.4rem 1rem;border:1.5px solid #1d3557;
       background:#1d3557;color:#fff;border-radius:7px;cursor:pointer;}
button.ghost{background:#fff;color:#1d3557;}
button:disabled{opacity:.35;cursor:not-allowed;}
.log{font-size:11.5px;color:#4b5563;border-top:1px solid #e5e7eb;padding-top:6px;
     max-height:86px;overflow-y:auto;line-height:1.8;}
.log-entry{padding:0;}
.done-banner{background:#d1fae5;border:1.5px solid #10b981;border-radius:8px;
             padding:10px 14px;font-weight:700;color:#064e3b;margin-bottom:8px;font-size:13px;}

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Column generation demo — set-cover LP on 4 items with 6 columns.
//
// Instance (verified by hand):
//   Items: {1,2,3,4}
//   Columns:  P={1,2} cost 4  Q={3,4} cost 4
//             R={1,3} cost 3  S={2,4} cost 3
//             T={1,4} cost 2  U={2,3} cost 2
//   Optimal: T+U = cost 4  (covers all 4 items)
//   Initial basis: P+Q (expensive, cost 8)
//
// LP dual prices (verified):
//   Iter 0: duals all 2 → RC(T)=-2, RC(U)=-2 (most negative), RC(R)=RC(S)=-1
//   Iter 1: basis P,Q,T; duals y1=0,y2=4,y3=4,y4=0 → RC(U)=-6 (most negative)
//   Iter 2: basis P,Q,T,U; solution xT=1,xU=1,xP=0,xQ=0; duals all 1
//           RC(P)=2, RC(Q)=2, RC(R)=1, RC(S)=1 — all non-negative → OPTIMAL

const ITEMS = [1,2,3,4];
const ALL_COLS = [
  {id:'P', items:[1,2], cost:4},
  {id:'Q', items:[3,4], cost:4},
  {id:'R', items:[1,3], cost:3},
  {id:'S', items:[2,4], cost:3},
  {id:'T', items:[1,4], cost:2},
  {id:'U', items:[2,3], cost:2},
];

// Pre-verified LP states at each iteration.
// Each state is shown AFTER that iteration's LP solve and BEFORE/AT the pricing step.
const STATES = [
  {
    // Iteration 0: initial restricted LP with P,Q only.
    active: ['P','Q'],
    x: {P:1, Q:1},
    obj: 8,
    duals: {1:2, 2:2, 3:2, 4:2},
    allRC: {P:0, Q:0, R:-1, S:-1, T:-2, U:-2},
    enter: 'T',        // most negative reduced cost
    enterRC: -2,
    note: 'Iter 0: basis {P,Q}, obj=8. Dual prices: all 2. Most negative RC: T and U both −2. Enter T.'
  },
  {
    // Iteration 1: LP with P,Q,T. T has zero value; xP=1,xQ=1 still forced.
    active: ['P','Q','T'],
    x: {P:1, Q:1, T:0},
    obj: 8,
    duals: {1:0, 2:4, 3:4, 4:0},
    allRC: {P:0, Q:0, R:-1, S:-1, T:2, U:-6},
    enter: 'U',        // RC=-6
    enterRC: -6,
    note: 'Iter 1: T entered but obj still 8 (items 2,3 force P,Q). RC(U)=−6 — most negative. Enter U.'
  },
  {
    // Iteration 2: LP with P,Q,T,U. Optimal: xT=1,xU=1,xP=0,xQ=0 → cost 4.
    active: ['P','Q','T','U'],
    x: {P:0, Q:0, T:1, U:1},
    obj: 4,
    duals: {1:1, 2:1, 3:1, 4:1},
    allRC: {P:2, Q:2, R:1, S:1, T:0, U:0},
    enter: null,       // no negative RC → optimal
    enterRC: null,
    note: 'Iter 2: U entered. Now xT=1,xU=1,xP=0,xQ=0 → obj=4. All reduced costs ≥ 0. OPTIMAL!'
  }
];

function getCol(id){ return ALL_COLS.find(c=>c.id===id); }

function coveredItems(activeIds, xMap){
  const cov = new Set();
  for(const id of activeIds){
    if((xMap[id]||0) > 1e-9) getCol(id).items.forEach(i=>cov.add(i));
  }
  return cov;
}

function renderItems(covSet){
  document.getElementById('items-display').innerHTML =
    ITEMS.map(i=>`<span class="item-chip${covSet.has(i)?' covered':''}">${i}</span>`).join('');
}

function renderActiveCols(active, xMap, entering){
  document.getElementById('active-cols').innerHTML = active.map(id=>{
    const col=getCol(id), xv=xMap[id]||0;
    const cls = id===entering ? 'entering' : (xv>1e-9 ? 'in-basis' : 'dropped');
    return fmt('<span class="col-chip %cls%" title="cost %cost%">%id%<span class="cc-sub">{%items%} $%cost%</span></span>', { cls: cls, cost: col.cost, id: id, items: col.items.join(',') });
  }).join('');
}

function renderPool(active){
  const el=document.getElementById('pool-cols');
  const rest=ALL_COLS.filter(c=>!active.includes(c.id));
  if(!rest.length){el.innerHTML='<em style="color:#bbb;font-size:11px">all columns considered</em>';return;}
  el.innerHTML=rest.map(c=>fmt('<span class="col-chip" title="cost %cost%">%id%<span class="cc-sub">{%items%} $%cost%</span></span>', { cost: c.cost, id: c.id, items: c.items.join(',') })).join('');
}

function renderResult(st){
  renderItems(coveredItems(st.active, st.x));
  const xStr=st.active.filter(id=>(st.x[id]||0)>1e-9).map(id=>`x<sub>${id}</sub>=${st.x[id]}`).join(', ');
  const dStr=Object.entries(st.duals).map(([i,v])=>`y<sub>${i}</sub>=${v}`).join(', ');
  document.getElementById('rb-body').innerHTML=
    fmt('<div class="row">Solution: %xStr%</div><div class="row">Objective: <span class="hi">%obj%</span></div><div class="row">Duals: %dStr%</div>', { xStr: xStr, obj: st.obj, dStr: dStr });
}

function renderPricing(st){
  const box=document.getElementById('pricing-box');
  const body=document.getElementById('pb-body');
  box.style.display='block';
  if(st.enter===null){
    const rcLines=st.active.concat(ALL_COLS.filter(c=>!st.active.includes(c.id)).map(c=>c.id))
      .map(id=>{const rc=st.allRC[id]; return `RC(${id})=${rc}`;}).join(', ');
    body.innerHTML=fmt('<div class="row">%rcLines%</div><div class="row"><span class="hi-ok">All reduced costs ≥ 0. LP is optimal!</span></div>', { rcLines: rcLines });
    return;
  }
  const col=getCol(st.enter);
  const dsum=col.items.reduce((a,i)=>a+st.duals[i],0);
  const rcLines=ALL_COLS.filter(c=>!st.active.includes(c.id))
    .map(c=>{const rc=st.allRC[c.id];return `RC(${c.id})=<b>${rc}</b>`;}).join(' | ');
  body.innerHTML=
    fmt('<div class="row">Pool RCs: %rcLines%</div><div class="row">Best: <strong>%enter%</strong> = %cost%−(%map%) = %cost%−%dsum% = <span class="hi-neg">%enterRC%</span> → Add!</div>', { rcLines: rcLines, enter: st.enter, cost: col.cost, map: col.items.map(i=>`y<sub>${i}</sub>`).join('+'), dsum: dsum, enterRC: st.enterRC });
}

function addLog(msg){
  const log=document.getElementById('log');
  const d=document.createElement('div');d.className='log-entry';d.textContent=msg;
  log.appendChild(d);log.scrollTop=log.scrollHeight;
}

let iter=0, done=false;

function step(){
  if(done)return;
  const st=STATES[iter];
  renderActiveCols(st.active, st.x, st.enter);
  renderPool(st.active);
  renderResult(st);
  renderPricing(st);
  addLog(st.note);
  if(st.enter===null){
    done=true;
    document.getElementById('btn-next').disabled=true;
    const b=document.createElement('div');b.className='done-banner';
    b.textContent=fmt('Optimal! No improving column exists. Total cost: %obj%.', { obj: st.obj });
    const wrap=document.querySelector('.cg-wrap');
    wrap.insertBefore(b,document.querySelector('.btns'));
  } else {
    iter++;
  }
}

function reset(){
  iter=0;done=false;
  document.getElementById('btn-next').disabled=false;
  document.getElementById('pricing-box').style.display='none';
  document.getElementById('rb-body').innerHTML='Press "Next iteration" to begin.';
  document.getElementById('log').innerHTML='';
  const banner=document.querySelector('.done-banner');if(banner)banner.remove();
  renderItems(new Set());
  renderActiveCols(STATES[0].active,{},null);
  renderPool(STATES[0].active);
}

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

Click Next iteration to run one pricing step: the algorithm checks all remaining columns for the one with the most negative reduced cost, adds it to the restricted LP, and re-optimizes. When no column has negative reduced cost, the current solution is provably optimal — even though most columns were never considered.

The Real Complexity

Column generation is elegant, but its complexity depends on two separate pieces.

The master LP (the restricted problem with the current column set) is an ordinary LP. Each re-solve is polynomial — efficient simplex or interior-point methods apply.

The pricing subproblem asks: among all columns not yet in the model, is there one with negative reduced cost? If the pricing subproblem is easy (e.g., a shortest-path in a graph, as in vehicle routing), the whole algorithm runs in polynomial time. But if pricing is itself NP-hard — as it is for some cutting-stock variants — then the column generation loop is not guaranteed to be efficient.

In practice, three phenomena keep it fast:

  • Sparse optimal bases: a linear program with m constraints has an optimal basis of at most m columns, regardless of how many variables exist. Column generation exploits this — only those m columns ever need to enter.
  • Warm starting: each LP re-solve starts from the previous optimal basis, so successive solves are nearly free.
  • Early termination for integer programs: when combined with branch-and-bound (giving branch-and-price), column generation provides the LP relaxation at each node, and good columns found early propagate throughout the tree.

The status: column generation is a proven polynomial method for LPs when pricing is tractable. For integer programs it becomes a heuristic framework — powerful in practice, but without worst-case guarantees. The cutting-stock problem itself remains open regarding exact complexity for integer solutions, with connections to bin packing.

Where It Matters

Column generation is not a theoretical curiosity — it is the engine behind some of the largest optimization systems in the world:

  • Airline crew scheduling: each column is a crew pairing (a sequence of flights assigned to one crew). There are astronomically many pairings; column generation adds only the cheapest ones that can still improve the schedule. Airlines with thousands of flights use this daily.
  • Vehicle routing: each column is a route for one vehicle. The pricing subproblem finds the shortest feasible route given current dual prices — a constrained shortest-path problem solvable in polynomial time. This is how logistics companies optimize fleets in real time.
  • Cutting stock: a roll of material can be cut in countless patterns. Column generation adds only the patterns worth cutting. Gilmore and Gomory's 1961 paper on this problem launched the field.
  • Network design and telecommunications: channel assignment, wavelength routing, and bandwidth allocation all involve exponentially many path variables managed by column generation.
  • Integer programming in general: branch-and-price extends column generation to integer problems and is the state of the art for many hard combinatorial problems, including set cover and bin packing.

The common thread: whenever a problem's variables correspond to combinatorial objects (routes, patterns, schedules) and the number of objects is exponential, column generation is the natural tool.

Conclusion

Column generation embodies a powerful idea: the optimal solution to a huge problem often uses only a tiny fraction of all possible variables. By starting small and asking — at each step — whether any excluded variable could help, the algorithm zeros in on that tiny fraction without ever enumerating the rest.

The pricing subproblem is the heart of the method. When it is tractable, column generation turns seemingly impossible problems into routine computation. When it is hard, the framework still provides a principled way to attack problems that no other method can handle at scale.

The next time you board a flight or receive a package on time, there is a good chance that a column generation solver — pricing routes and schedules one column at a time — made that possible. For deeper connections, explore linear programming and bin packing, two of the pillars column generation rests on.

Share this article

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

Comments

Loading comments...

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