Cutting Without Waste

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.

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">{{hint}}</p>
<div class="order">
  <span class="lbl">{{lbl_order}}</span>
  <span id="pieces"></span>
</div>
<div id="bars" class="bars"></div>
<div class="meter">
  <div>{{lbl_bars_used}} <b id="nbars">0</b></div>
  <div>{{lbl_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">{{btn_add}}</button>
  <button id="opt" type="button">{{btn_optimize}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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.

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.

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.