Introduction

A workshop buys steel bars in a standard length — say 10 metres. An order comes in: so many 3-metre pieces, so many 4-metre, so many 6-metre. How do you cut the bars to fill the order using the fewest bars — and leaving the least scrap?

It feels like arithmetic. Cut a 6 and a 4 from one bar: perfect, zero waste. Cut two 4s and a 3 — that's 11, too long, so you cut two 4s and lose 2 metres. The choices multiply, and the leftover offcuts are pure loss: wasted metal, wasted money.

This is the cutting-stock problem, and it's a close cousin of bin packing — instead of fitting items into bins, you're fitting cut-lengths into fixed bars. Like bin packing, it looks tidy and turns out to be NP-hard. Get it right across thousands of orders and you save a fortune; get it wrong and the scrap bin overflows.

Cut the Bars

Try it. Each bar is 10 m long. The order needs the pieces listed below. Click a piece, then click a bar to cut it from that bar — it fits only if there's room. Watch the waste meter track the leftover.

<p class="hint">Bars are <b>10 m</b> each. Pick a required piece, then click a bar to cut it there (it must fit). Use <b>Add bar</b> for a fresh one. Minimize bars and <span class="w">waste</span> — then hit Optimize to compare.</p>
<div class="order">
  <span class="lbl">Order:</span>
  <span id="pieces"></span>
</div>
<div id="bars" class="bars"></div>
<div class="meter">
  <div>Bars used: <b id="nbars">0</b></div>
  <div>Waste: <b id="waste" class="w">0 m</b></div>
  <div id="msg" class="msg"></div>
</div>
<div class="btns">
  <button id="add" type="button">+ Add bar</button>
  <button id="opt" type="button">Optimize</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.hint .w { color: #c0392b; font-weight: 700; }
.order { margin-bottom: .8rem; }
.lbl { font: 600 13px system-ui; color: #555; margin-right: .4rem; }
.piece { display: inline-block; background: #457b9d; color: #fff; border: 2px solid #457b9d; border-radius: 6px; padding: .25rem .55rem; margin: .15rem; font: 700 13px ui-monospace, monospace; cursor: pointer; }
.piece.sel { background: #fff; color: #457b9d; box-shadow: 0 0 0 2px #457b9d; }
.piece.done { opacity: .3; cursor: default; text-decoration: line-through; }
.bars { display: flex; flex-direction: column; gap: .5rem; margin-bottom: .8rem; }
.bar { height: 34px; border: 1px solid #bbb; border-radius: 6px; background: #f1f3f5; display: flex; overflow: hidden; cursor: pointer; position: relative; }
.bar:hover { border-color: #457b9d; }
.seg { height: 100%; display: flex; align-items: center; justify-content: center; font: 700 12px ui-monospace, monospace; color: #fff; border-right: 2px solid #fff; }
.seg.s3 { background: #2a9d8f; } .seg.s4 { background: #e76f51; } .seg.s5 { background: #6d597a; }
.seg.s6 { background: #457b9d; } .seg.s7 { background: #b5651d; }
.bar .free { height: 100%; background: repeating-linear-gradient(45deg,#fbeeec,#fbeeec 6px,#f7ded9 6px,#f7ded9 12px); flex: 1; }
.meter { display: flex; gap: 1.2rem; align-items: center; font-size: .95rem; margin-bottom: .7rem; flex-wrap: wrap; }
.meter .w { color: #c0392b; }
.msg { color: #0a7d33; font-weight: 700; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Cutting stock: cut fixed-length bars into required pieces with least waste.
// NP-hard (generalizes bin packing). "Optimize" here runs Best-Fit-Decreasing,
// which finds the perfect 4-bar plan for this order.
const BAR = 10;
const ORDER = [6, 4, 5, 5, 7, 3, 4, 3, 3]; // total 40 -> 4 bars is optimal (0 waste)
let placed, bars, sel;

function reset() { placed = ORDER.map(() => false); bars = []; sel = -1; render(); }

function used(bar) { return bar.reduce((s, x) => s + x, 0); }

function renderPieces() {
  const el = document.getElementById('pieces');
  el.innerHTML = ORDER.map((len, i) =>
    fmt('<span class="piece%v%" data-i="%i%">%len%m</span>', { v: placed[i] ? ' done' : (sel === i ? ' sel' : ''), i: i, len: len })).join('');
  el.querySelectorAll('.piece').forEach(p => p.addEventListener('click', () => {
    const i = +p.dataset.i; if (placed[i]) return; sel = (sel === i ? -1 : i); render();
  }));
}

function renderBars() {
  const el = document.getElementById('bars');
  el.innerHTML = bars.map((bar, b) => {
    const segs = bar.map(len => '<div class="seg s' + len + '" style="width:' + (len / BAR * 100) + '%">' + len + '</div>').join('');
    const free = BAR - used(bar);
    const freeDiv = free > 0 ? '<div class="free" style="flex:' + free + '"></div>' : '';
    return '<div class="bar" data-b="' + b + '">' + segs + freeDiv + '</div>';
  }).join('') || '<div style="color:#999;font-size:.9rem">No bars yet — Add bar, pick a piece, then click the bar.</div>';
  el.querySelectorAll('.bar').forEach(bar => bar.addEventListener('click', () => place(+bar.dataset.b)));
}

function place(b) {
  if (sel < 0) { flash('Pick a piece first.'); return; }
  const len = ORDER[sel];
  if (used(bars[b]) + len > BAR) { flash('Doesn’t fit on that bar.'); return; }
  bars[b].push(len); placed[sel] = true; sel = -1; render();
}

let msgTimer = null;
function flash(t) { const m = document.getElementById('msg'); m.style.color = '#c0392b'; m.textContent = t; }

function render() {
  renderPieces(); renderBars();
  const waste = bars.reduce((s, bar) => s + (BAR - used(bar)), 0);
  document.getElementById('nbars').textContent = bars.length;
  document.getElementById('waste').textContent = fmt('%waste% m', { waste: waste });
  const m = document.getElementById('msg');
  const allDone = placed.every(Boolean);
  if (allDone) {
    m.style.color = '#0a7d33';
    m.textContent = bars.length <= 4 ? fmt('✓ Order complete with %length% bars — optimal!', { length: bars.length }) :
      fmt('✓ Order complete with %length% bars (4 is possible).', { length: bars.length });
  } else if (msgTimer === null) { m.textContent = ''; }
}

// Best-Fit-Decreasing: place each piece (largest first) on the bar that
// leaves the least leftover; open a new bar only if none fits.
function optimize() {
  const items = [...ORDER].sort((a, b) => b - a);
  const result = [];
  for (const len of items) {
    let best = -1, bestRem = Infinity;
    result.forEach((bar, i) => { const rem = BAR - used(bar) - len; if (rem >= 0 && rem < bestRem) { bestRem = rem; best = i; } });
    if (best < 0) result.push([len]); else result[best].push(len);
  }
  bars = result; placed = ORDER.map(() => true); sel = -1; render();
}

document.getElementById('add').addEventListener('click', () => { bars.push([]); render(); });
document.getElementById('opt').addEventListener('click', optimize);
document.getElementById('reset').addEventListener('click', reset);
reset();
Result
Console

Try to use the fewest bars with the least waste, then hit Optimize to see a tight plan. The natural "biggest piece first" instinct often strands awkward leftovers — exactly the trap that makes cutting stock hard.

The Hard Part

Here's why the scrap bin resists:

  • Checking a cutting plan is easy: sum each bar's cuts, confirm none exceed its length, add up the waste.
  • Brute force is hopeless: the ways to combine cut-lengths into bars grow exponentially.
  • It's NP-hard. Cutting stock generalizes bin packing (a "bin" is a bar, an "item" is a cut). Bin packing is already NP-hard, so this is too.
  • The clever idea is column generation. In 1961 Gilmore and Gomory reframed it: instead of listing every possible cutting pattern up front (there are astronomically many), generate only the patterns that actually help, guided by linear programming. This Gilmore–Gomory method still powers industrial cutting optimizers.
  • In practice solvers combine column generation, integer programming and rounding heuristics to get within a hair of optimal on real orders.

So like its cousin bin packing, cutting stock is provably hard, yet a beautiful LP-based trick tames it well enough for the factory floor.

Where It Matters

Anywhere raw material comes in standard sizes and gets cut to order, this problem is money:

  • Metal and pipes: cutting steel bars, rebar and tubing to construction specs.
  • Paper and film: slitting giant master rolls into the widths customers order.
  • Glass, wood and textiles: cutting sheets, boards and fabric with minimal offcut.
  • Manufacturing: stamping parts from stock plate or coil.
  • Sustainability: less waste means lower cost and a smaller footprint — the same optimization helps the bottom line and the planet.

Because a percent of saved material across millions of cuts is huge, cutting-stock optimization is a mature, valuable corner of industrial software.

Conclusion

Cutting stock is a quiet hero of industrial math. The question — cut these bars with the least waste — sounds like a chore for a tape measure, yet it shares its NP-hard core with bin packing, and the choices explode the moment the order gets real.

What makes it inspiring is the fix: Gilmore and Gomory's column generation doesn't fight the exponential head-on, it grows only the cutting patterns worth considering. It's a textbook case of theory paying off — a provably hard problem, solved well enough every day to save factories material, money and waste.

Share this article

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

Comments

Loading comments...

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