Cutting Wood using Optimization

In this post an interesting problem was described:

• Raw material is a number of lengths of wood types A,B,C and D.
• We want to cut it so we can create final product. This final product consists of combos of wood types A,B,C and D of the same length.
• The final product can not be shorter than 30.
• In the post it was requested to produce a cutting scheme such that left over raw material of length less than 30 (waste) is minimized.

If we would just use this objective (minimize waste) the optimal strategy would be “don’t cut anything”. Therefore our first approach is to use a slightly different objective: create as much final product as we can. Later on we will discuss some refinements.

As usual there is more than one way to skin a cat, here is just one way of doing that. First introduce our basic “assignment” variables and the index sets they operate upon:

The assignment structure follows from these fundamentals.

1. The first equation is used to make sure that exactly one raw piece is used for each wood type in a final product. We introduce a binary variable y_j to keep track which j’s are actually created (typically we have more j’s in the model than needed: we don’t know this number in advance).
2. Equation (2) deals with the length of the final product combo. Note that L_j does not depend on the wood type w. So all pieces in the combo have the same length. Note that this final product combo length is actually a decision variable. 
3. Inequality (3) simply makes sure δ_w,i,j=0 ⇒ x_w,i,j=0.
4. Finally inequality (4) deals with raw material lengths. This L_i is a constant.

The data set we will use is:

This means in the model we do not want to use all combinations (w,i) but rather a subset wi(w,i). A complete model setup can look like:

The model equations are:

Notes:

• The variables L_j are declared integer, just to get nicer solutions.
• The order equation helps producing nicer reports but also helps in speeding up things.
• We solved with Cplex with some extra options:
• Threads to allow parallel B&B
• Mipemphasis to indicate we want to go to optimality
• Priorities on the discrete variables to help Cplex a bit
• The solution time was < 2 minutes (to proven optimality).

The final results look like:

The rows represent the raw material and the columns are the final product combos. Each column should have exactly four entries (one from each color or wood type). The columns are ordered by length and the smallest length is 30. On the right we verify that we have never exceeded the raw material length. In this solution we have used up all the yellow (wood type C) raw material.

Objective

The proposed objective in the original post is:

(1) Minimize Waste 

where waste is left over cuts with a length < 30. The problem with this objective is that “doing nothing” would be an optimal solution.

In our model we used the objective:

(2) Maximize total length of final product

Actually this is not such a bad choice. We can see we use up the yellow wood type C (this has a smallest amount of raw material) without any waste.

If we know the demand for the final product we can use the following model:

(3) Minimize Waste
    Subject to meeting demand 

If we don’t know demand in advance and the final product is made for inventory, we can use a different approach. We assign dollar values to both raw material lengths and final product lengths. Of course a raw material length length of < 30 gets a zero value (or may be a small scrap value). Now we can do:

(4) Maximize Total Value 

We can refine this further by assigning different values to different lengths, so we can favor longer lengths.