The classical "partition problem" asks how many ways one can write a given natural number as a sum of smaller numbers. One variant of this would be to ask if a positive real number can be expressed as a sum of given smaller but positive real numbers.
I am interested in a similar problem that comes up in carpentry.
Say I want to cut a sheet of wood into several smaller pieces of wood. I know the geometry of the smaller pieces of wood I would like to cut my large sheet of wood into. Both the input and desired output (to keep things reasonable) are all rectangular. How do you decide if it is possible to make the cuts?
To add a little realism to the question, what if we further posit that the cutting operation is a strict "loss" operation, and a certain amount of the material is lost along the cut -- this is the width of the saw/cutting blade. You also know (ahead of time) the geometry of the wood you start with. Perhaps there's more than one sheet you start with. Frequently one buys sheets of wood with near identical geometry at wood shops. So one's input in this question is a rectangular wood type with a particular geometry (length and width), and a desired output of a list of boards with their own particular lengths and widths. We want to know the minimal number of input boards to buy, and how to cut them.
I know how to answer this question for any given input parameters. It tends to be a rather exhaustive process, like the classical partition problem but far more time consuming as there is more choice.
Has anyone written software that does the work for you, and gives you some cutting diagrams for such "perfect" ways to cut wood?
Given all the lovely smart CNC machines out in the world, I imagine there are some nice smart algorithms available. But I don't know where to look.
I'm asking this question because I'm about to invest in some wood to make some furniture, and I'd like to certify I'm wasting as little wood as possible.
There has been quite a bit of work on this practical shape-packing problem, but I am not certain I know the latest advances. And I do not know if there is any but commercial software available. Here is a bit of information.
First, nearly every version of the problem of packing shapes (polygons) into a region (usually a rectangle or an infinite strip) is NP-hard, so various heuristics are used in the general case, or restrictions are imposed in special cases. An example of the former is using simulated annealing after an initial approximate packing. Here are two instances of the latter. In the first paper below, the shapes packed are restricted to convex polygons, which still leaves the problem NP-hard. Then it is further restricted to just two polygons, and an $O(n^3)$ algorithm is obtained:
Victor Milenkovic pursued packing (nonconvex) shapes on infinite strips of cloth for the garment industry in a series of publications. The paper below restricts to (a) translations only, and (b) lattice packings. The problem still hard, but good practical results can be achieved:
Concerning software, I know of NestLib and SigmaNest. Given this situation, you might just use some greedy bin-packing algorithm and adjust by hand.