Last weekend, I decided to build a bed. I looked up some plans online, made some modifications, drew up a list of the lengths and sizes of lumber I needed, and went to the store to buy lumber. That’s when the trouble started. The Lowe’s near me sells most of the wood I needed in 6ft, 8ft, 10ft, and 12ft lengths, with different prices. And I needed a weird mix of cuts – ranging from only 10 or 11 inches up to 5 feet. How was I supposed to know which lengths to buy, or how many boards I needed?
Of course, I could have just planned out my cuts on a sheet of paper, gotten close to something that looked reasonable, and called it a day. But I figured there had to be a better way. Turns out, there is, and there’s a huge body of academic literature on the subject. The problem I was facing was simply an expanded version of the classic “cutting stock problem.” It’s a basic integer linear programming problem that can be solved pretty easily by commercial optimization software. So, I decided to try out some optimizations!
Setting up the problem
There’s a lot of (commercial and open-source) software that will run this optimization problem for you. I initially chose to go with Excel’s built-in Solver plugin, but found that its non-linear solvers were both inefficient, and tended to find solutions that weren’t actually optimal – just “locally optimal.” (If you’re not familiar with the language and concepts of linear programming, Wikipedia’s linear programming article is a good place to start.) So, I decided to go bigger… I have previous experience with the integer programming solver provided by PROC OPTMODEL in SAS, and I figured it would get the job done in no time!
The first step was to build some dummy data in SAS. I needed one data set of available lumber, showing the length I could purchase, and the price for that length. I then needed another data set that contained the length of cuts I needed for my project, with the required quantity. Here’s my dummy data (note that it’s not actually the real data for my project, just some dummy numbers I put in to test this out).
The next step was to frame the problem in a way that it could be submitted to PROC OPTMODEL. Basically, I figured the best way to accomplish this would be to create a data set of every possible pattern of cuts I could take out of a board, and the associated cost of that board. So, I could take an 8″ cut out of a 72″ board and nothing else. Or 2 8″ cuts. Or 3. Or an 8″ cut and a 13″ cut. On and on, ad nauseum, for every combination of cuts and boards. I accomplished this in a SAS data step. The code below also includes some macro code for counting the number of available lumber types and types of cuts needed, so that the code can scale for bigger or smaller problems…
This left me with a list of every possible option I could cut, and the associated price for the board I’d be cutting out of. Now, all that was left was to optimize!
The dummy data shown here generates hundreds of patterns that could feasibly be cut from the available lumber. So, it’s pretty easy to frame the optimization problem… All we need to do is choose how many of each possible pattern we want to produce. Obviously, we’ll choose 0 of most patterns. We want to do this in such a way that we minimize the total cost of our purchase. And we’re bounded by two constraints. First, the total number of each resulting cut has to equal the total number needed for the project. Second, we can’t have less than 0 of any particular pattern. That’s all there is to it!
PROC OPTMODEL makes it very simple to describe these constraints, and run the optimization. Here’s the code!
SAS solves our dummy problem in only a couple hundredths of a second. Not bad – it certainly blows Excel Solver out of the water! The optimal solution to the dummy problem costs $53.50, and requires us to cut 7 different patterns – 6 out of 72″ lumber, and one out of 96″ lumber. You can see the results below. Pretty cool!
If you’re looking to save some money on a woodworking project, optimizing your lumber purchases is a good way to go. Of course, the code provided above leaves a few things out. You can’t trust that wood sold as “10 foot” at the hardware store is exactly 10 feet. Also, each time you cut a board, you lose a little bit of length to the width of the saw blade. You could certainly compensate for this in the model above by shaving a few inches off the length of each piece of lumber in your input. Or you could choose to model this in, if you wanted!
Either way, it’s pretty clear that PROC OPTMODEL is a great way to solve this problem – and dozens like it. Of course, at some point, the problem will get too large and the software will choke. There’s some techniques in the literature for getting around that, but I didn’t bother to implement them here. Suffice it to say that, for most everyday home projects, this should work out just fine! And, besides, the learning was the main point here anyway.