math/geometry/construction query!

October 6, 2016 7:59 PM

Suppose you have to install new moulding in a house. Suppose also that it's a huge house with many rooms large and small, and many windows of different size. This means that you end up needing many different lengths of wood...

So you've done all the measuring and you have a long list, and it's time to order the wood. The wood is available in one length, say ten feet. So here's my question:

How do you most efficiently divide your different lengths between the ten-foot sections with the least leftovers? (And in the process find out the minimum you need to buy)

I know you could do it all "manually", starting with the longest cuts and seeing what fits the leftovers, but...

Isn't there some online tool for this? Or some Excel thing? It seems like such a fundamental thing, the efficient use of material, that somebody somewhere has worked out something for it. But I've gotten nowhere with Google. I don't even know what to ask it (you may not know the answer, but if you can even supply the name for the problem, that'd at least give me a lead).

posted by Rich Smorgasbord to Technology (14 answers total)

Best answer: This is known as the "knapsack problem" in computer science.
posted by dilaudid at 8:03 PM on October 6, 2016 [3 favorites]

Best answer: subset sum problem (a special case of the knapsack problem)
posted by zippy at 8:16 PM on October 6, 2016

I think you are forgetting all the pieces that get cut the wrong way or are too short or just don't fit right. Buy extra!
posted by H21 at 8:25 PM on October 6, 2016 [3 favorites]

Best answer: I came in to say Bin Packing problem, but I am extremely interested in hearing how carpenters / people who actually do this type of work, wrong cuts and all, make their estimates.
posted by batter_my_heart at 8:49 PM on October 6, 2016 [2 favorites]

You'll certainly want a couple of percent reserved for cock-ups! Also, how many joins do you want to see? This is both an aesthetic choice and a skill query (if done well they can be nearly invisible).

But no, I have faced this challenge many times but have never thought that there may be an answer out there apart from working it out for yourself. A materials estimator/quantity surveyor is the expert in this field. Hopefully one will come along?
posted by wilful at 8:58 PM on October 6, 2016

The answer, batter, is that it depends on whether you're using stock trim profiles or custom profiles, say to match existing trim in an older home. With stock trim, you order what you know you need and a little extra, try to make cuts efficiently, and return any extra to the lumberyard. With custom profiles generally you need to be more conservative since they can't be returned.
posted by Makwa at 8:59 PM on October 6, 2016 [1 favorite]

Response by poster: For the sake of the purely geometric problem (and whether there's a way to answer it online or somewhere), assume there are no wrong cuts or whatever else.
posted by Rich Smorgasbord at 9:13 PM on October 6, 2016

Best answer: I used this calculator once. Or rather, I think I used it because I found it in my bookmarks...
posted by pipeski at 3:37 AM on October 7, 2016 [1 favorite]

I came in to say Bin Packing problem, but I am extremely interested in hearing how carpenters / people who actually do this type of work, wrong cuts and all, make their estimates.

Stone and tile installers, and roof tile installers, that I've worked with typically order 10-15% more than just the raw square footage that they need to cover, but they have to worry about breakage as well as wrong cuts or defective material, so a finish carpenter could probably get away with ordering a bit less over the raw linear footage of molding.
posted by LionIndex at 5:09 AM on October 7, 2016

This could also be a cutting-stock problem.

However, I think most carpenters would use a heuristic, i.e. blunder through, by using the smallest piece they have which will work. This could be augmented by the ability to scarf sections together so the join is not noticeable.
posted by SemiSalt at 5:52 AM on October 7, 2016

pipeski - that calculator is odd, in that it "assumes that longer stock is cheaper per inch", which not only makes the problem more complicated, but is generally wrong.
posted by mr vino at 5:57 AM on October 7, 2016 [1 favorite]

mr vino, in my experience, longer stock tends to be cheaper per inch up to the point where you're looking at really long stock, which is obviously harder to produce, and therefore comes at a premium. You can try the calculator with whatever stock lengths you like, though - it's trivial to run a few different stock-length scenarios.
posted by pipeski at 6:25 AM on October 7, 2016

I'm not sure if there is a real-life situation behind this hypothetical one, but in practice what people do is just buy long pieces of moulding stock (sixteen footers are pretty normal) and start cutting and installing them. Whenever you end up with a piece at the end of a length of stock that you can't use right then but which you think might be usable later, you put it to the side. You end up with a small pile of odd-sized pieces in addition to your main stockpile of full-length ones. For each cut you try to take it from the shortest piece that's long enough to do the job, meaning that you only break out a new full-length piece of stock if there isn't an odd-sized piece that's big enough.

The above system isn't rigidly adhered to. If you realize that you're about to make a bunch of cuts that will perfectly use up one of the pieces you have on hand then you may do that, for instance. Since many of your cuts will be basically the same, you'll gradually get a feel for what kinds of combinations will work well and you'll look for opportunities to use pieces of stock more efficiently. And of course people aren't perfect, so sometimes there are variations just due to random chance.

At the end, you wind up with a bunch of very short offcuts, none of which are long enough to be useful for anything, and probably a few full-length pieces which you return to the lumber yard and get your money back for. It's probably not perfectly optimal, but you'd be surprised how close it can get. A skilled carpenter will leave very little waste using the method I've described.
posted by Anticipation Of A New Lover's Arrival, The at 8:11 AM on October 7, 2016 [2 favorites]

I've watched my stepfather the carpenter do this, and Anticipation is correct. It's not a situation where you say to the lumberyard, "I'd like 317.5' of trim, please." You do a either a rough estimate in your head (if the amounts are small at the material is cheap) or a careful one on paper (if it is a lot of material or very pricy) and then you buy enough 16-footers to cover that total number plus a little extra. There is also generally the assumption that you can return extras or go pick up a few more if you run out, so there is never too much pressure to be exact.
posted by Rock Steady at 8:30 AM on October 7, 2016