Algorithm for fitting boards to available lengths, minimizing waste

Question

I'm writing an application to use in the lumber yard. Given a number of board or beam lengths, the goal is to calculate the number of boards needed while minimizing waste. For example, one might have the following shopping list for one particular dimension:

3x 2.9 meters
5x 1.6 meters
21x 0.9 meters

At the lumber yard, one would check the available lengths of boards and enter it into the application. Lets say that this dimension is available in 4.8 meters lengths.

A simple approach would be to try and fit the remaining boards in descending lengths:

2.9 + 2.9 = 5.8 so that won't fit on a 4.8 meter board
2.9 + 1.6 = 4.5 so that's ok.

No length is less than the remaining 0.3 meters so this board is "full". We will fit two more of this type, and then we have the following lengths left to fit:

2x 1.6 meters
21x 0.9 meters

Ok, so this algorithm works reasonably well. But what if we instead of fitting the 2.9 + 1.6, we fit 2.9 + 0.9 + 0.9 = 4.7 instead. We will then get 0.1 meters waste per board, instead of 0.3 meters.

One problem in enumerating all possible combinations is that each length might appear more than once in a board, and the number of lengths fitted in a board will vary as well. Is there a known algorithm I can use to minimize the total waste for all boards?

Also, what if there are two or more lengths available at the lumber yard? For instance 5.4, 4.8 and 3.6 meters? This will surely complicate things. One could run the selected algorithm for each available length and pick the length with the least amount of waste. But the most elegant solution would allow mixing the available lengths, so the optimum answer might be something like 1x 5.4, 3x 4.8, 6x 3.6. But for starters, I would be happy with limiting the the answer to one length.

Answer 1

Minimizing the waste is actually optimization problem for generalized subset sum problem, which is NP-Complete, and thus there is no known polynomial time solution for this problem,

Though NP-Complete, one can produce pseudo-polynomial solution for this problem using dynamic programming, or reducing it to knapsack (weight=value=length, W=board size), and use its pseudo-polynomial solution, which is very similar.

However, in here it is even trickier, the pseudo-polynomial solution assumes integers, while your examples show this is not the case. You can solve it by using fixed point arithmetics to represent the lengths (i.e. 4.8 will be displayed as 48, if you are using only one digit after the dot per length, if you are using 2 digits after the dot, it will be 480,...).

Note: this algorithm will minimize the waste for you, but it doesn't guarantee "minimum number of logs" for the minimized waste.

In any case, since finding any solution is NP-Hard, finding the solution that uses least logs is also NP-Hard.

Answer 2

Your particular problem is a variant of the so-called "Cutting Stock" class of problems. Take a look at Wikipedia's "Cutting Stock Problem" (CSP) page

I like this explanation in plain English of a simpler version of the Cutting Stock Problem. From AIMMS:

"Cutting stock problem: how to cut long rolls of material (referred to as raws) into smaller rolls of a prescribed size (referred to as finals), given a demand for each of the finals."

This pdf by AIMMS is good.

Note that there are quite a number of variations to the Basic Cutting Stock Problem that researchers have come up with. These Integer Programming lecture notes good formulation of the generalized Cutting Stock problem (see page 17)

These MILP problems are not very difficult to formulate because the objective function and the constraints follow the basic pattern of the standard CSP. A huge body of research exists on techniques to solve them efficiently.

If you have access to an LP/IP solver such as CPLEX, R, or the Excel Solver (for smaller problems), it is definitely worth formulating your problem and trying it on these solvers.

Hope that helps.