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 whether any plan does better, and hands you the working so you can check that for yourself. Everything happens in this page. Nothing is uploaded.
x 4 to say you only have four of them, and
@ 18.40 to give a price. So 3600 x 4 @ 25.90.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.
When the plan matches 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".
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.
| Population | Lists | First-fit lost a board | Bound unreachable |
|---|---|---|---|
| Furniture, 2.4 m stock, parts 250 to 1900 mm | 2000 | 5.50% | 0 |
| Framing, 4.8 m stock, parts 300 to 2400 mm | 2000 | 26.15% | 0 |
| Parts all near half a board | 2000 | 0.00% | 0 |
| Uniform synthetic, the textbook regime | 2000 | 10.45% | 1 |
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.
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.
Three ways, because a checker that only agrees with itself has not checked anything.
research/cut-list/bench-results.md.1,438 assertions:
node research/cut-list/verify-cut-list.mjs