The Cutting Stock Problem, Explained with a Real Cut List

The cutting stock problem is the task of cutting a list of required pieces from standard-size stock (bars, boards, rolls or sheets) so that the least stock is used, or equivalently the least material is wasted. Every cut list optimizer is a solver for some version of it.

Three things define an instance:

• The stock: one or more standard sizes, such as 8 ft 2x4s, 20 ft steel tube or 4×8 plywood sheets.
• The demand: each piece size and how many you need (8 rails at 45", say).
• The rules: kerf lost at every cut, and for sheets, whether cuts must run edge to edge (guillotine) and whether grain limits rotation.

The answer is a set of cutting patterns, each one a recipe for a single piece of stock ("one 72" and one 21""), together with how many times to repeat each pattern.

It is a close relative of bin packing. Our bin packing guide covers that side, including the common heuristics. The difference is one of emphasis. Bin packing usually treats every item as distinct, while cutting stock assumes you need many copies of a few sizes. That's what makes the pattern view work, and it's why cutting stock is the right model for a shop cut list.

The problem is older than computers, and it started with plywood.

• 1939, Leonid Kantorovich. Working on production planning for a Leningrad plywood trust, Kantorovich published Mathematical Methods of Organizing and Planning Production, which formulated cutting and allocation problems as what we now call linear programs. He shared the 1975 Nobel Memorial Prize in Economics for this line of work.
• 1961 and 1963, Paul Gilmore and Ralph Gomory. Their papers "A Linear Programming Approach to the Cutting-Stock Problem" (parts I and II, Operations Research) made it practical. The key idea is column generation. Rather than listing every possible cutting pattern up front (there can be astronomically many), you solve a linear program over a small set of patterns, then solve a knapsack subproblem to find one new pattern that would improve the plan. You add it and repeat until no pattern helps.
• 1965, Gilmore and Gomory again. "Multistage Cutting Stock Problems of Two and More Dimensions" extended the approach to sheets cut in stages of edge-to-edge cuts, which is still the classic model of the guillotine constraint panel-saw users know.

Column generation, wrapped in branch-and-price when you need a proven optimum, is still the textbook method for 1D cutting stock with high demand. Many shop-oriented tools, EZNESTING included, use fast heuristics instead. They return an answer in seconds, and for typical shop lists that answer is often provably optimal, as the example below shows.

Here's a real list: the frame of a 72"-tall, 48"-wide, 24"-deep garage shelving unit in 2x4.

• 4 uprights at 72"
• 8 front/back rails at 45"
• 8 side rails at 21"

Stock: 8 ft (96") 2x4s. Kerf: ⅛".

Step 1: the lower bound. Total length needed is 4 × 72 + 8 × 45 + 8 × 21 = 816". Divide by 96" and you get 8.5, so no plan can use fewer than 9 sticks, however clever it is. This bound is the single most useful number in cutting stock. It tells you how close to perfect any answer is.

Step 2: patterns. A 96" stick can hold, for example:

• 72 + 21 (leaves 2⅞" after one ⅛" kerf)
• 45 + 45 (leaves 5⅞")
• 45 + 21 + 21 (leaves 8¾")
• 21 + 21 + 21 + 21 (leaves 11⅝")

Step 3: the plan. Running the list through EZNESTING's linear optimizer returns 9 sticks:

That is 9 sticks, which matches the lower bound, so it is optimal. No tool can do better on this list. Material yield is 816" ÷ 864" = 94.4%. EZNESTING's results panel shows 94.6% average utilization, because it also counts the ⅛" kerfs as used material.

Notice what the patterns are doing. Every upright gets a 21" side rail as its partner, because 72 + 21 is the tightest fit on a 96" stick, and that's exactly the pairing a Gilmore–Gomory pattern search would look for. The leftover 21s share one stick. Open linear mode with an 8 ft 2x4 loaded, enter the three cuts, and you'll get the same plan.

The lower bound isn't always reachable, and that's where the "cutting" part becomes a real problem rather than a division.

Take a steel railing: 36 pickets at 41½" and 6 rails at 94½", cut from 20 ft (240") tube with a 1/16" kerf. Total length is 2,061", and 2,061 ÷ 240 = 8.6, so division says 9 sticks.

But look at the patterns that fit a 240" stick. The useful ones are:

• 2 rails + 1 picket (230½" of parts)
• 1 rail + 3 pickets (219")
• 5 pickets (207½")

You need 6 rails, so the rails must use up some sticks. Across 9 sticks, every combination of these patterns that covers 6 rails leaves room for at most 33 pickets, and you need 36. So 9 sticks is impossible, and the true minimum is 10. EZNESTING returns exactly 10: three sticks of pattern one, six of pattern three, and one stick with three pickets and a 115⅜" drop you can put back on the rack.

This gap between the area (or length) bound and the integer answer is why cutting stock is hard. For a small list you can reason it out as we just did. As the number of sizes grows, the number of pattern combinations explodes. Formally, the problem is NP-hard: no known algorithm is guaranteed to find the optimum on every list in time that grows only polynomially with its size. See the bin packing guide for what that means in practice. Real solvers either search cleverly (column generation, branch-and-price) or use heuristics that are fast and usually at or near the bound.

1D cutting stock has one dimension that matters: length. Lumber, pipe, tube, bar, extrusion, trim. Patterns are just lists of lengths that add up (with kerf) to no more than the stick.

2D cutting stock cuts rectangles from sheets or panels. Plywood, MDF, melamine, sheet metal, glass. It's harder in every way. A pattern is now a layout, rotation may or may not be allowed (grain), and the cut sequence matters:

• Guillotine cuts run edge to edge across the current piece. Panel saws, track saws and table saws work this way. Gilmore and Gomory's multistage model is exactly this: rip into strips, then crosscut the strips, then (maybe) trim.
• Non-guillotine layouts can interlock pieces so that no single straight cut separates them. They can pack tighter, but you can only cut them with a CNC router, laser or waterjet, never with a saw.

The same lower-bound trick works in 2D with area. In our kitchen cabinet example, five frameless 24" base cabinets need 103.75 sq ft of 3/4" parts. Divided by 32 sq ft per 4×8 sheet, that's 3.24, so at least 4 sheets, and the optimizer lays it out on exactly 4 (details in how many sheets of plywood for kitchen cabinets).

For how guillotine and free layouts compare on the same parts, see guillotine vs free cuts.

EZNESTING doesn't run column generation. Here's what it actually does, straight from the engine:

• Linear (1D): First Fit Decreasing. It sorts cuts longest first and packs each stick as full as it can, skipping a piece that won't fit and trying the next shorter one, before it moves to the next stick. With several stock lengths it fills the longest sticks first. Kerf is subtracted at every cut.
• Sheets (2D): a guillotine packer that tries several sort orders (and rotation on and off, where grain allows) on each sheet and keeps the layout that places the most area. It also runs the job with the sheet turned 90° and keeps the better run. A second mode, Fewest cuts, aims for simpler strip layouts and faster sawing.

These are heuristics. They are fast and deterministic, but they don't guarantee the optimum on every list. That's why the lower bound matters. When the stick or sheet count equals the bound, as in the shelving example, you know the answer can't be beaten. When it's one above, like the railing, a quick pattern check tells you whether the gap is real.

Want to try your own list? Open the linear optimizer or switch to sheet mode for panels. Free: unlimited optimizations, up to 5 part sizes and 3 stock sizes per job, with every optimizer feature included (kerf and trim, grain direction, edge banding, CSV/Excel/DXF import, and PDF, CSV, Excel and DXF export). No signup needed to try it.