# Practical Cutting Stock Problem

Warning. This post is for an audience of close to zero. My technical friends will find this pretty basic, and my non-technical friends will find this too technical. Welcome to the middle space that I occupy between these two worlds.


I wanted to build this series of retaining walls to replace the overgrown ivy and eroding slope next to my stairs in my front yard.

One of the challenges of my current job is to keep my skills sharp as a program manager. I decided to find an automated solution, even when the practical solution was pretty obvious. My problem was basic, I had to make the following cuts:

• 43 1/8
• 4' 7/8
• 44.5" x 3

As these were landscape timbers, I knew that I could get them at Home Depot in 8, 10 or 12 foot lengths at $20.57,$29.97, or $37.27. The longer lengths cost more at 2.57, 3, and 3.11 a foot. To minimize my cost, I wanted to buy the least number of pieces and at the shortest lengths possible. I solved this in 2 minutes in excel, by just guessing and found that I could do one 8 and one 12 or three eights. Three eights would be$62 and and 8,12 would be $58. I'm going to pay the$4 and get pieces I can more easily move, and get 4 more feet to play with.

However, isn't this a nice knapsack problem for the excel solver? I thought I would give it a try. Google showed me this quick refresher and Wikipedia provides a nice start and the integer program can be formulated as:

$$\min\sum_{i=1}^n c_i x_i$$ $$\text{s.t.}\sum_{i=1}^n a_{ij} x_i \ge q_j, \quad \quad \forall j=1,\dots,m$$ $$x_i \ge 0, \text{integer}$$

where $$a_{ij}$$ is the number of times order $$j$$ appears in pattern $$i$$ and $$c_i$$ is the cost (often the waste) of pattern $$i$$.

However, I wanted to be quick. I didn't want to have to find all patterns ahead of time. After playing around for a couple minutes, I got this working in excel using a genetic algorithm by forcing each cut to only happen once and minimizing the amount spent.

With these constraints:

Solver Parameters

While I had a quick solution under my belt, I waited until a long plane flight to cook up something better. First, I skimmed through these papers:

For me, it turns out the key to solving this is to come up with a list of potential patterns and to solve for the pattern combinations in order to get the quantities right. First, I used Matlab to come up with feasible combinations by using the and the very handy allcomb function to generate all possible combinations and removing those that were too long.

{aaa01f1184b23bc5204459599a780c2efd1a71f819cd2b338cab4b7a2f8e97d4} here 3 cuts are hard-coded
M = allcomb([0:max_num], [0:max_num], [0:max_num]);

{aaa01f1184b23bc5204459599a780c2efd1a71f819cd2b338cab4b7a2f8e97d4} now reduce to the feasible solutions
F = M(M*cuts' < max_length, :);

{aaa01f1184b23bc5204459599a780c2efd1a71f819cd2b338cab4b7a2f8e97d4} remove the trivial
F = F(2:end,:);


First, I implemented this in Excel using their simplex solver.

With the following solver constraints:

I also implemented an end-to-end solution in Matlab that should be useful for my next project. This way I understand the math behind it and can use my optimizer for any number of projects.

This produces an output like:

board: 1 | quantity: 1 | 2 cuts of 44.5  waste: 7
board: 2 | quantity: 1 | 1 cuts of 44  waste: 52
board: 3 | quantity: 1 | 1 cuts of 44 1 cuts of 44.5  waste: 7.5
board: 4 | quantity: 2 | 1 cuts of 44 1 cuts of 49  waste: 3
----------------------
Total waste: 72.5 inches


And I added some graphics to be able to guide my cuts.

## 5 Replies to “Practical Cutting Stock Problem”

1. Jim Muccio says:

Or another solution would be to call me…I’ve got like 15 8ft 6×6 timbers I could have given you at half price…

2. Jim Muccio says:

First, I’m glad you recognized that this problem falls under an entire discipline of cutting stock problems vs the classic knapsack formulation. Second…you’ve still not included the possibilities I mentioned above. One, you can get the cuts for free at the Depot, thus solving your transportation problem. Two, once, your transportation problem is solved you will significantly reduce your waste…thus it will have to be a cheaper option.

3. Phil says:

First off, congratulations on tackling the problem with mathematics and software! Kudos to you. I am squarely in your “minimum audience” zone as I often encounter issues when renovating that can be solved empirically but I always enjoy the challenge of solving the “properly” with computers. My partner often accuses me of over engineering the solution, something I am secretly proud of. It is one thing to think you have the best solution, it is another thing altogether to be absolutely sure you have the optimal solution.
I do have a question that you might be able to provide some insight on or at least point me in the right direction. I believe it falls under the cutting stock problem (CSP), but I cannot find a good solution on the internet. This particular problem relates to the deck I am building:
I need to combine a finite number of lengths of decking timber (15 different lengths of varying quantities) to form 6600mm strips to cross my deck, however, they can only be butt joined at the joists, which are at specific spacing’s. The second part of this problem is then laying out the 6600mm “strips” in a way that staggers the joins for a) strength and b)visual appeal. I think it might qualify as a 1.5 dimensional CSP but I cannot find any one discussing it. I appreciate your thoughts on the matter.
Cheers

4. Al says:

Thanks for publishing this work. I am also in the group that wants to know if I’m doing something optimally or not (and has the time to fiddle with it).
I took your MATLAB function, ported it to Octave 5.2 and extended it to allow for multiple stock sizes.
Using a demand of cuts = [44 49 44.5]; quantity = [3 1 3]; and allowing 8′, 10′ and 12′ lumber, I got a solution with two 8 footers and one 12 footer with a waste of only 21.5 inches. I could get the Excel evolutionary solver to produce the same solution but had to be careful about how I added the additional lengths. I love Excel but wouldn’t recommend it in this case.

5. Hussaan says:

Excellent work. Kindly share the excel file to find all patterns using Solver.
Thanks
My email
hussaan1986@gmail.com

This site uses Akismet to reduce spam. Learn how your comment data is processed.