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:
- Cutting Stock with Binary Patterns: Arc-Flow Formulation with Graph Compression
- Improving Branch-And-Price Algorithms For Solving One Dimensional Cutting Stock Problem
- The Cutting Stock Problem by UNC
- AIMMS Modeling Guide – Cutting Stock Problem — this one addresses multiple stock lengths
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.
Please share any comments/insights.
Leave a Reply