Linear Programming: The Stock Cutting Problem
This article is a deep dive into how linear programming can solve a specific problem called the ‘stock cutting' problem. I want to provide a concrete example before getting too deep into the details linear programming in this series. This article will use Optimization terms that are not defined in it – I wrote an optimization basics article that covers those terms and other basic concepts.
In this article, we'll go over:
- Stock cutting problem definition
2. Problem difficulty
3. Solving the problem in Python
Here are the links to the first article in the series and the optimization basics article I mentioned:
Stock Cutting Problem Definition
The stock cutting problem is a very practical and applicable problem. The first article I ever wrote on TDS covered a greedy algorithm that I wrote to help me reduce waste when doing my own woodworking projects. The greedy algorithm was sufficient for little DIY projects, but linear programming can solve the stock cutting problem at an industrial scale!
Here is the setup for the problem. Imagine that you are making a piece of furniture. For the piece, you need multiple cuts of wood of various lengths. The lumber yard only sells wood of one length. The stock cutting problem can optimize the cutting strategy so that you buy as few pieces of wood as possible – which saves you money and minimizes waste.
Here's a simple example of a stock cutting problem. Let's say you need to make the following cuts (borrowing the example I made in my first article on the subject): [6′, 6′, 5′, 4′, 3′, 3′] and the store sells stock pieces that are 9′ long. The stock cutting problem asks, "What cutting strategy should we use to minimize the number of stock pieces we need to purchase?"
Before we get into how linear programming can help us solve this problem, let's look at how a bad strategy can cost us money.
This specific instance of the problem is pretty simple and can easily be optimized by hand. But let's just imagine we didn't think the problem through or made a mistake when developing the strategy below, which requires purchasing 4 pieces of stock:
In the solution above, we get all of the required cuts, but we need to purchase 4 pieces of stock. Below is the optimal strategy which meets all of the required cuts, but only requires 3 pieces of stock to be purchased. The takeaway here is that optimizing the strategy can save real world money!
For this toy example, finding the optimal solution is very easy. But the challenge with the stock cutting problem is that as you add more cuts (think at an industrial scale) the problem gets extremely difficult to solve. And that is where linear programming can help us out. Let's first get some intuition on why the stock problem cutting problem gets difficult with scale.
Stock Cutting Problem Difficulty
What makes the stock cutting problem difficult is the fact that adding more cuts vastly increases the size of the solution space. So, as the problem scales up, it quickly becomes intractable.
You can think of the stock cutting problem as an ordering problem. You are placing the cuts in a specific order. To execute a plan, you go through pieces of stock making cuts in the specified order – once the cut off piece is too short for the next cut, you start cutting a new piece of stock.
The number of unique ways to order n items (or in this specific case, cuts) is n!. Factorials grow extremely quickly. Below is a table I borrowed from my first article on the stock cutting problem to illustrate this point:
The above table shows the size of the solution space if we are going to try to solve the problem directly via a brute force or greedy algorithm. When we use linear programming, we need to adapt our approach to the problem in a way that the solution space is smaller and there is not closed form solution (like the factorial function) to easily quantify the size. We'll cover all of those specifics in the next section!
Solving an example problem in Python
As we've now established, the stock cutting problem is really hard to solve because of the very large number of potential solutions to explore. Luckily, we can use the power of linear programming to help overcome these challenges. Unluckily, for the stock cutting problem to fit into the linear programming paradigm, we have to make a few concessions. Let's get into it!
If you recall from the first article in the series (or your basic knowledge of linear programming) – linear programming problems have a linear objective function and usually have linear constraints (if it is a constrained optimization problem). So, to encode the stock cutting problem into a linear programming problem, we need a way to create an objective function and constraints that make sense. We do this by providing the problem with pre-defined cut patterns – if that doesn't make sense now, don't worry about it, we'll break it down!
What is a cut pattern you may ask? It is simply a plan for how to cut a single piece of stock. We showed multiple cut patterns in our quick example in the intro. The suboptimal solution (showing again below) gave us four unique cut patterns.
The catch with using linear programming is that we have to provide the cut patterns. Typically, if we are solving a problem that is hard enough to justify the use of linear programming, there are too many potential cut patterns to include them all in the problem. This will have some implications on the interpretation of the final optimized results – but we'll get to that later!
For now, let's use the four cut patterns established above to finally set up our linear programming problem. The problem will be deciding how many times to use each cut pattern. So, for example, if the problem decides to use cut pattern 1 three times, we will get three 5′ cuts and three 3′ cuts at an expense of three stock pieces. Following this structure, we want to minimize the number of patterns we use (objective) while making sure we have all of the cut lengths we need (constraints).
In the optimization function, we create a decision variable for each cut pattern. The variable values are the number of each cut pattern to use. Here is our objective function formally written out:
Now, let's add the constraints. We need a constraint for each length of cut. As a reminder, we need these cuts for our project: [6′, 6′, 5′, 4′, 3′, 3′]. We'll use 6′ as an example; our constraints need to ensure that the solution provides at least two 6′ cuts. We need to look at each cut pattern to see how many 6′ cuts each has. The table below shows the break down:
From here, it is really easy to convert this into a linear constraint.
Following the same process, we can make a constraint for each cut length. Okay, so the full set up for the problem looks like this:
Let's turn to Python to actually solve this problem! We'll set it up and solve it using the pulp library:
import pulp
# Define the problem
lp_problem = pulp.LpProblem("stock_cutting", pulp.LpMinimize)
# Define decision variables
x1 = pulp.LpVariable('x1', lowBound=0)
x2 = pulp.LpVariable('x2', lowBound=0)
x3 = pulp.LpVariable('x3', lowBound=0)
x4 = pulp.LpVariable('x4', lowBound=0)
# Objective function - minimize stock purchases
lp_problem += (x1 + x2 + x3 + x4)
# Constraints
lp_problem += x2 + x3 >= 2, "6 foot cuts"
lp_problem += x1 >= 1, "5 foot cuts"
lp_problem += x1 + x2 >= 1, "4 foot cuts"
lp_problem += x4 >= 2, "3 foot cuts"
# Solve the problem
lp_problem.solve()
# Output the results
print("Status:", pulp.LpStatus[lp_problem.status])
print("Optimal number of stock purchases:", pulp.value(lp_problem.objective))
print("Optimal use of cut patterns:")
print("x1 =", pulp.value(x1))
print("x2 =", pulp.value(x2))
print("x3 =", pulp.value(x3))
print("x4 =", pulp.value(x4))
Congratulations! You've now solved the stock cutting problem with linear programming – you may have some reservations about the our approach though. I certainly do! Let's talk about a key concern:
Key Concern – results depend on cut patterns passed into optimization
The linear programming will always find the best solution given the cut patterns provided. It will not find the global best solution, unless all of the cut patterns required for the global best solution are available. This can be a challenge because, depending on the specifics of the problem, there can be a lot of unique cut patterns. Thankfully, including a good spread of cut patterns will usually be easier than solving the stock cutting problem itself.
There isn't a closed form solution to calculating the total possible number of cut patterns because number of cuts on a specific piece of stock is variable. We can, however, follow a simple algorithm (which works well for small stock lengths and a short cut list) to calculate the number of unique cuts.
Here are the steps in the algorithm:
- Calculate the maximum possible number of cuts for a cut pattern
- Iterate through all cut patterns with the maximum number of cuts – eliminate patterns that are not feasible or duplicates.
- Go down one cut from the previous number of cuts and repeat steps 2 and 3 recursively.
- After all feasible, unique cut patterns have been created, remove sub-optimal patterns – defined as cut patterns that could have an additional cut.
I'm about to go into a lot of detail about how we can find all of the possible cut patterns for an instance of the stock cutting problem. This focuses on the specifics of the problem and not so much on the linear programming aspect. If this isn't what you signed up for, feel free to skip down to the section titled ‘running the linear programming problem with all cut patterns.'
Let's use our current example to illustrate the algorithm:
For the first step we'll calculate the maximum number of cuts that can go into a cut pattern. To do this, we take our cut list and sort from shortest to longest. Which is [3, 3, 4, 5, 6, 6] – then we sum up the lower cuts until the sum is greater than the stock length. In our case, we add 3+3+4 = 10 – so the maximum number of cuts for our patterns is 2, because we can add at most two cuts to a single pattern (3 + 3).
Now we are ready for the second step. For this step, we find all of the unique combinations of two cuts from our list (the total count of unique combinations is 6 ‘choose' 2):
Then, we eliminate duplicates and patterns that are not feasible (cuts that add up to > 9):
After eliminating duplicate and infeasible cut patterns, we are left with 5 unique patterns:
With the first and second step complete, the third step is to repeat the process but with one less cut on the stock. Since we had two cuts last time, we will do 1 cut now. This will go as follows:
Now that we have iterated through all possible patterns, and we've removed duplicate and infeasible patterns, we have one final step. Step four is to remove sub-optimal cut patterns. Sub-optimal is defined as cut patterns that could have an additional cut. For example, if we have the cut pattern that just has a 3′ cut, this is sub-optimal because it could also have an additional 3′ cut, or a 4′ cut or even a 6′ cut. It is sub-optimal because it is leaving cuts on the table for no reason. Including these ‘sub-optimal' cut patterns won't hurt our optimization solution. But, including them will slow down our optimization run time and create unnecessary complexity.
We check for sub-optimal solutions by simply looking at the cuts that remain after a pattern and see if the shortest one would fit in the pattern. If any cut does fit in the pattern, the pattern is sub-optimal and we eliminate it. The logic here is that a cut pattern that fits that description has waste that could be used for another cut, so there is no reason to not just use a cut pattern that has the original cut, plus the additional cut.
After all of that work, here is our final list of cut patterns:
This algorithm works well for very simple problems like our example. In fact, we were able to calculate all of the cut patterns by hand! But, as the number of cuts grow, this can quickly become intractable. When that happens, we will have to employ some kind of a heuristic based algorithm to come up with a subset of good cut options rather than creating an exhaustive list. The code in the linked repo (https://github.com/jaromhulet/stock_cutting_lp) has a class I wrote the uses the neighborhood-based hill climb algorithm to identify potential cut pattern candidates. Going into the details of that algorithm is beyond the scope of this article.
Running the linear programming problem with all cut patterns
Now that we have the 5 possible cut patterns, let's re-run the optimization and see what the results are.
Here is the new formulation with all of the optimal cuts included:
And here are the results. As we can see, improving the cuts that are available in the LP problem gives us a better solution – we only need to buy 3 stock pieces instead of 4!
The key takeaway here is that the LP will always find the optimal solution, given the cut patterns provided. For simple problems, we can provide all cut patterns that make sense (unique and not sub-optimal), but for larger problems we have to take a subset of good cut patterns. If we provide a subset, linear programming will solve the problem well given the subset, but we may not get the global optimal solution. Spending time improving the subset could improve the solution, like in our example!
Conclusion
The purpose of this article was to give a concrete, real-world and in-depth application of linear programming. This is a powerful tool that is used across many domains and industries. Often, as with the stock cutting problem, the real challenge lies in how you formulate the problem to fit into the rules of linear programming. Once you have a solid understanding of how linear programming works, you can understand and find clever ways to encode problems (like the stock cutting problem) into the LP paradigm and thus take advantage of the optimizing power it has!
