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.

Retaining Walls

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.

Excel Solver Example

With these constraints:

Solver Parameters 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.

Improved 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.

matlab_results

Please share any comments/insights.

3 thoughts on “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…

    However, you’ve missed the fact that you could cut the timbers in place at Home Depot thus eliminating your transport problem… So the correct answer is to buy one 8, buy one 12, and make your first cut at the Depot. Also, you could ask Home Depot to make all your cuts…thus really reducing your ability to move those things. Sometimes they will…sometimes they will not particularly with treated lumber…but you could bring your cross cut and knock it out in 5 minutes. You’ve under constrained your problem but not eliminating the 10 ft lengths…and then ignored that you really want another 4 ft of bonus timber. Your true formulation however would call for that extra 48 inch timber that you will use for another project (to play with)…since you see value in it. Thus 3 8ft timbers is the correct solution if you see value in the waste product.

  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

Leave a Reply

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