For developers
The 1D cutting stock problem
How to cut a set of required lengths from stock bars using the fewest bars is the 1D cutting stock problem: a classic, genuinely hard optimisation problem. Here is what it is, why it resists brute force, and how it is solved in practice, including in the API behind this site.
What the 1D cutting stock problem is
You are given stock pieces of a fixed length (say 6000 mm bars) and a list of required pieces, each with a length and a quantity. A cutting pattern is one way to cut a single stock bar into some of those pieces; whatever length is left over is waste. The problem is to choose patterns, and how many bars to cut on each, so that every required piece is produced and the total number of stock bars, equivalently the total waste, is as small as possible. One dimension, because only length matters: the blade runs across the whole cross-section, so width and profile never enter the packing.
1D bin packing, and why it is NP-hard
The cutting stock problem is a generalisation of 1D bin packing: bin packing asks you to pack a set of distinctly sized items into the fewest fixed-size bins, and cutting stock is the same question once items repeat in large quantities, so you reason about patterns rather than individual items. Bin packing is one of the classic NP-hard problems, and its decision form, can these items fit in k bins, is NP-complete. Cutting stock inherits that hardness.
The reason is combinatorial explosion. The number of distinct cutting patterns grows exponentially with the number of part sizes, and the number of ways to spread quantities across those patterns explodes on top of that. There is no known algorithm that finds the guaranteed optimum in time that scales polynomially with the input, and unless P equals NP there is not going to be one. So real solvers do not enumerate everything; they are clever about which possibilities they can rule out.
How it is solved in practice
First-fit-decreasing (FFD)
The workhorse heuristic: sort the required pieces longest to shortest, then place each one on the first bar it still fits, opening a new bar only when none has room. It is fast and surprisingly good, provably within about 11/9 of the optimal bar count plus a small constant. Most tools stop here; a good one uses FFD as a starting point, not the finish line.
Column generation (Gilmore and Gomory)
The formulation that made large instances tractable. Gilmore and Gomory (1961) wrote the problem with one variable per cutting pattern and, since there are exponentially many, solved the linear relaxation by delayed column generation: start with a handful of patterns and repeatedly generate the next most useful one by solving a bounded knapsack subproblem. The lower bound it produces is famously tight.
Branch-and-bound and branch-and-price
To turn that fractional relaxation into a whole number of bars you have to search, but not blindly. Branch-and-bound explores the tree of integer choices while using the LP bound to prune whole branches that cannot beat the best plan found so far; combined with column generation it becomes branch-and-price, the basis of most exact cutting stock solvers.
Lower bounds, and a proof
A serious solver does not just return a plan, it computes a lower bound (from the LP relaxation, or a simpler total-length argument) and compares. When a plan uses exactly as many bars as the bound proves are unavoidable, it is provably optimal: no plan can do better, and the solver can say so instead of hoping it got lucky.
How LinearCutting solves it
LinearCutting runs this stack: a fast heuristic for an instant feasible plan, then a bound-driven search that keeps improving until it either matches the lower bound (provably optimal, and it tells you) or spends its time budget and returns the best plan it found. It models the physics too, kerf on every cut, end trim, fixed-quantity offcuts and angled cuts that consume extra, because a plan that ignores the blade is not merely suboptimal, it is wrong. The benchmark jobs are published so you can check the results against any other tool.
It is exposed as a JSON API: send your parts and stock, get back a verified cutting plan with the layouts, the waste, the setup count and whether the plan hit the optimal bound. There are official clients for Python (pip install linearcutting) and JavaScript or TypeScript (npm install linearcutting), so calling it is a few lines in either language.
Solve it from your code
Skip writing a solver and call one. The same engine behind this site's calculator is a JSON API with official Python and JavaScript clients, a free public tier, and a live example you can run in the docs.
pip install linearcutting npm install linearcutting