I was recently posed the question, “Can you use Mathematical Planning to optimize the Cutting Stock problem?” For those who are not familiar with this problem, you can find the Wikipedia article here. In summary, you have a stock size of paper material from which you need to produce smaller sizes. In the example provided on Wikipedia, the stock size is 5600mm. You are asked to produce a variety of sizes between 1380mm and 2200mm. The ideal plan is one which minimizes the amount of waste. This is a classic planning problem that can actually be reduced to the knapsack problem.
Note: Full code for this post can be found here
These are the cut lengths and quantities you need to produce in the example problem.
|Width [mm]||Number of Items|
There are a variety of different ways you can cut the stock size into the smaller sizes. For example, you could produce 3 x 1820mm cuts from a 5600mm stock roll. You could also do 2200mm, 1820mm, and 1560mm. In total there are 308 possible combinations of cuts, not including the empty combination which has zero cuts. The most important thing to realize when approaching this problem is that the order you make the cuts does not matter. A more technical term would be that the order of cuts is commutative.
Generating the Possible Cuts
The most difficult part of this problem turned out to be the generating of the possible cuts. Before we dive right into that though, let’s create some simple domain types to describe our problem.
Cut is a length we want to create from our stock rolls. A
Plan is a set of cuts. We want an algorithm which will generate the possible
Plans for a set of
Cuts for our stock roll. To make our lives easier, I am going to go ahead and write some functions which allow us to work with these types more easily.
We now have our domain for working in this space. Let’s talk about the function which will generate the possible
Plans given a set of
Cuts and a Stock Length. We want something like this:
Now, I’m going to show you the answer that I came up with. What you are not seeing though is the couple of hours I spent with my notebook sketching out how this would work. It was not intuitive to me, so I don’t want you to think that this stuff just materializes out of thin air. I had to struggle. It was not intuitive but by the time I was done, I felt immense satisfaction.
The first thing I am going to do is sort
cuts from the shortest length to the longest and ensure that I only have distinct cuts.
This algorithm is going to take advantage of the fact that the cuts are sorted from shortest to longest so that it can terminate early. Now I want to write a recursive function which is going to take an initially empty
Plan and try adding cuts to it. It will keep adding cuts until it exceeds the Stock Length. You can think of this as a sort of Constructive Heuristic. I’m going to show you the full function but then we will unpack it.
We have a list of plans and possible cuts which we are exploring called
candidates. As candidates are approved, they are added to the
approved list of plans. Keep in mind, this function will be initially called with an empty
Plan and the full list of
Cuts available. Let’s go through the cases step by step.
This is the terminal case. We have evaluated all the
Plans that were generated, and we return the
Plans in the
approved list. Now for the case where we still have remaining candidates.
In this case, there is at least one remaining candidate to evaluate,
testCandidate. We create
cuts values using structural unpacking of
plan is the
Plan we are testing.
cuts is the list of possible cuts we can add to
plan. You will see that this list will shrink as our algorithm continues.
Now let’s match against the list of
Cuts to see what we should do.
If the list of cuts is empty, as indicated by the
 case, then we create
newApproved by adding
approved and calling
generate again. Now let’s look at the case where there are
We now look at
nextCut which we know is the shortest of the
Cuts in the list due to our sorting. We check that if we add this
plan whether we will exceed the
stockLength limit. If we do not exceed the limit, we create a new plan
newPlan. We will add
newPlan to the list of
cuts as the list of possible
Cuts to explore. We also add the current
Plan we are testing,
plan, to the list of
candidates but now with
remainingCuts as the possible
Cuts to add. Take your time with that. That puzzle took me awhile to figure out.
In the case that the length of
nextCut is too long, we add
approved and then continue to search the remaining
We call our recursive function with an empty
Plan to start and the full list of
Cuts to get all the possible
Plans we would want to consider.
The Optimization Problem
The optimization model for this is rather simple. We will create the list of possible
Plans using the function we just described. We will associate an integer
Decision with each
Plan which is to indicate how many of each of those plans we will schedule. Let’s setup the data for our model so that we can build it. All this data is taken from the Wikipedia example.
We now want to start building our model. We’ll open the namespaces we need and create our set of
Decisions associated with each
plans. We are using SliceMaps to simplify formulation.
We then need to calculate the number of each
Cut that is associated with each
Plan. This will be important for us to formulate the constraints around meeting the minimum cut requirements. We will store this information in a 2-D
SliceMap where the first index is the
Plan and the second index is the
Cut. The value in the
SliceMap is the number of a given
Cut in the
It’s now actually simple to create our constraints. We will create a constraint for each
Cut in our data stating that the solution must meet the minimum quantity of each
Our objective is to minimize the total number of stock rolls required to meet the demand for each
We combine these into our model and solve.
Let’s go ahead and provide some nice printing of the results to the console.
When you run the full script, you will see the following printed out.
If you check the Wikipedia article, you will see that the best possible answer is 73. There are multiple, equally good solutions. This is called Degeneracy. Problems with high levels of Degeneracy can be difficult to solve but fortunately this one was not. You may run this code on your machine and get a different set of plans, but you’ll still have a total of 73 stock rolls required.
This was a fun challenge and was a bit of a brain teaser. These types of problems are everywhere in manufacturing planning and scheduling. Minimizing the amount of raw resources required is incredibly important but can be brutally difficult. It’s often done by domain experts spending hours with Excel finding a plan that meets all the requirements. These are some of my favorite problems to turn into Mathematical Planning models. Thank you for your time and I look forward to chatting next week!
Please send me an email at firstname.lastname@example.org if you have any questions and subscribe so you can stay on top new posts and products I am offering.