Give it your stock, your blade and your parts. It returns a cutting plan, and then does the half that usually gets left out: it tells you the most that any plan, found by anyone, could ever save against it, and hands you the working so you can check that for yourself. Often that figure is zero, and then the plan is the best there is. When it is not zero it is still an answer, and usually a small one.
Your stock, your blade and your parts never leave this page: the arithmetic runs in your browser, there is nothing to sign in to, no limit on how many parts you may have, and it keeps working with the network off. (The site counts the page view, and nothing else.)
x 4 to say you only have four of them, and
@ 18.40 to give a price. So 3600 x 4 @ 25.90.
Offcuts you already have go here too, priced at zero: 1240 x 2 @ 0 means two
drops on the shelf, and a plan will use them before it buys anything.0 if it does not apply.6 x 46 1/2. Lines starting with # are ignored.A cutting plan is easy to check. Add up the parts on each board, add a blade width for each cut, and see that it fits. This page does that to its own answer before showing it to you, and refuses to print a plan that fails.
The hard half is the other direction: could some cleverer plan use fewer boards? For any but the shortest lists there are more ways to divide the parts across boards than anyone can look at, so the honest way to close that question is not to search harder. It is to produce a number, and an argument that the number cannot be beaten.
The argument is short enough to walk through. Suppose I hand you one small non-negative weight for each part size, and you satisfy yourself of a single fact: no single board can hold parts whose weights add up to more than one. You can check that yourself by trying to fill one board as heavily as the weights allow. Once you believe it, the rest is arithmetic. Every plan has to cut all the parts, so the plan's boards must between them carry the whole weight of the list; and no board carries more than one. So the plan needs at least total weight boards, rounded up. Whatever the plan is. Whoever made it.
Those weights are the optimal solution of a linear program dual to the cutting problem, and finding good ones is Gilmore and Gomory's 1961 idea, which is still how the problem is solved. But you do not have to take the linear program's word for anything: the weights arrive as whole numbers over a common denominator, and the check that no board can exceed one is run here in exact integer arithmetic, by code that never sees where the weights came from. The certificate panel above prints them, and the button re-runs that check on the numbers as displayed. Floating point proposes; integers decide.
Two things get rounded up in that paragraph and only one of them is sound, so it is worth separating them. Rounding the bound up is sound: a plan uses a whole number of boards, so if the weights prove that no plan costs less than 5.67 boards, no plan uses fewer than 6. Assuming that a plan exists at 6 is not sound, and this page never assumes it. It goes and finds one, or it tells you it could not.
When the plan meets the certificate, the answer is settled and you can hand the certificate to somebody else. When it does not, this page falls back to an exhaustive search over every way of filling a board, and says so, because "we looked at all of them" is a weaker thing to be told than "here are ten numbers, check them".
Most cut-list tools have one thing to say when they cannot prove their plan is best, which is nothing. This one says how much is left. If the certificate proves that no plan costs less than 63,373 mm of steel and the plan in front of you buys 63,500, then 127 mm is the most that any plan, found by anyone, by any method, on any machine, could ever save you. That is a complete answer to the question a person actually has, which is not "is this optimal" but "is it worth my Saturday to keep fiddling with this".
It also stops a fact about arithmetic from masquerading as a fact about the search. A board count is a small whole number, so a plan lands exactly on its floor constantly. A length in millimetres is a fractional combination of whatever stock lengths you own, and a plan almost never lands exactly on that, however good it is: the floor sits between the lengths you can actually buy. A tool that reports only settled-or-not therefore looks brilliant on one question and useless on another, when nothing about it has changed. The interval is the same measurement in both cases, and it is honest in both.
One thing it does not say, and the distinction matters. "No plan costs less than 63,373 mm" is a statement about the floor. It is not a promise that 63,373 is reachable: it usually is not, because you cannot buy 0.02 of a bar. So the page says what it can prove, in those words, and leaves the rest alone.
The standard way to plan a cut list is to sort the parts longest-first and drop each into the first board it fits. That is first-fit decreasing, and it is a good method: fast, obvious, and usually right. The question worth asking is how often usually is not enough, which is a measurable thing rather than an opinion, so it was measured. (This page does not claim to know what any particular planner does inside; it measures the method, not the competition.)
Four populations of cut lists were drawn at random, each shaped to look like a different kind of real work, and each one settled to proved optimality by the engine on this page. They are reported separately and never pooled, because the answer depends far more on the population than on the method.
What that sentence is scoped to, because it is easy to read it as wider than it is: every list in those four populations has one stock length and is asked for the fewest boards. That is the corner of the problem where the plan and the floor are both small whole numbers, and it is the corner where they meet most easily. Ask the same lists for the least material off a merchant's range of six lengths and far fewer settle outright, not because the search is worse but because the floor now falls between two boards you can buy. Those jobs get the interval instead, and the interval is usually a fraction of one board wide.
| Population | Lists | First-fit lost a board | Bound unreachable |
|---|---|---|---|
| Furniture from 2.4 m stock | 2000 | 5.50% | 0 |
| Framing from 4.8 m stock | 2000 | 26.15% | 0 |
| Parts near half a board | 2000 | 0.00% | 0 |
| Uniform synthetic | 2000 | 10.45% | 0 |
Two things in that table are worth more than the headline. The first is that the rate swings from one list in four to none at all, so any single number anybody quotes for "how much greedy costs you" is a number about their test set. The second is the row that reads zero: when every part is near half a board, first-fit never loses, because there is nothing to be clever about. The regime that looks hardest is the one where the obvious answer is forced.
Reproduce: node research/cut-list/population.mjs --n 2000 --time 3000.
The draw is seeded, so the numbers come back the same.
Round the certificate up and you have a number of boards. Almost always, a plan exists that hits it exactly, which is why this page can usually settle a job outright. Almost always is not always, and the exceptions are strange enough to be worth meeting. How rare is measurable rather than a matter of opinion: across the eight thousand lists in the table above, drawn to look like four kinds of real work, the rounded-up certificate was unreachable not once. You have to build these instances on purpose.
Here is one, and it is small enough to hold in your head. Twelve pieces, and boards eighteen units long. The pieces add up to 89. Five boards hold 90. There is a whole unit to spare, and there is no five-board plan.
Whether a cut list can ever need two whole boards more than its own linear relaxation says is an open question: the modified integer round-up conjecture of Scheithauer and Terno, which the 2015 paper this instance comes from left, in its authors' words, "still widely open". That paper raised the largest slack anyone had exhibited to 1.0625 boards and recorded that no instance with a slack of two was known. Later papers have pushed the record up; this page has not read them, so it does not quote a figure. Your kitchen shelves are not going to settle it. But it is the reason this page will not simply round the bound up and call the job done: rounding up is a guess, and the search that follows it is not.
It is also a hard ceiling on what this method can ever prove, and the ceiling is measurable rather than hypothetical. Of the twenty-eight instances Schoenfield built in 2002 specifically to defeat good packing methods, five have a relaxation whose rounded-up value is one below the optimum: BPP14, BPP119, BPP175, BPP359 and BPP716. Column generation was run to convergence on each of them here, with no clock, and agrees. On those five no weights exist that could certify the true answer, however clever the search that found the plan. So the honest maximum for a certificate on that set is twenty-three of twenty-eight, and a page that quoted twenty-eight as its target would be quoting a target that does not exist. Establishing that number before writing any sentence about a score is the whole difference between a measurement and a boast.
Three ways, because a checker that only agrees with itself has not checked anything.
research/cut-list/bench-results.md, alongside where this
engine sits against the published heuristics on the hardest set.1,734 assertions:
node research/cut-list/verify-cut-list.mjs. A count of assertions says nothing about whether any
of them can fail, so there is a second instrument that breaks the engine sixteen ways on purpose and requires
the red light each time: node research/cut-list/mutate.mjs. Its first run caught seven of the
sixteen and it now catches thirteen; the three it does not are tuning parameters that no instance can be
found to distinguish, and it says so rather than pretending. Every survivor is written up in
research/cut-list/README.md, including one defect it found that had been introduced an hour
earlier, and three mutations that turned out not to mutate.