We address a common modelling issue: The solution is optimal, but not practical.
In our situation, the stated objective is to minimize trim waste in our paper manufacturing process. This is a type of coverage optimization problem. There is a theoretically perfect solution, with zero waste, but it is impractical to implement due to its complexity.
So, in reality, we have two intertwined objectives that we need to satisfy:
Quantitative: Minimize trim waste in our manufacturing process.
Qualitative: Make the solution simple and practical.
We can model the quantitative objective, but the qualitative objective has at least equal importance. Having an optimal, but impractical, solution is common in real-world optimization problems. The conflict between perfect and practical makes our situation both challenging and interesting.
In this series of articles, we use a variety of techniques to create several models. Along the way, we address the trade-off between our quantitative and qualitative objectives, enabling the decision maker to make an informed decision to implement an efficient and practical solution.
Articles in this series
The articles in this "Optimal but not practical" series are:
First attempt. Model 1: Non-linear model that finds optimal solutions for small data sets, but not for the full data set.
Linear, partial data set. Model 2: Linearized model using a small sub-set of the full data. Finds local optima.
Full data set. Model 3: Extends Model 2 to use the full data set. Finds globally optimal solutions, but requires a large amount of memory.
Column generation. Model 4: Variation of Model 2, with randomly-generated columns. May find globally optimal solutions, though not guaranteed to do so.
Either/or BigM. Model 5a and 5b: Explicitly models rotation of the items using BigM constraints. Three times larger than Model 3, so difficult to solve.
Either/or Disjunction. Model 5c: Explicitly models rotation of the items using Pyomo's Generalized Disjunctive Programming (GDP) extension.
Virtual machine. We set up a Google Compute Engine with 128 GB of RAM to run Model 3 on data sets larger than we can run on our local modelling computer.
Download the model
The models described in this series of articles are built in Python using the Pyomo library.
In our paper manufacturing process, we produce 100 unique paper items. Each item is rectangular with known width and length. We also know the annual order quantity for each item.
The items are cut from larger stock paper products. These stock products can be made for us in any size we want. The width and length of a stock product must be greater than or equal to the item size that is cut from it. Our manufacturing process requires that only one item is cut from each stock product. The stated objective is to minimize the waste from trimming the stock products to make items, weighted by the annual quantity of each item.
Given this statement of the situation, the optimal solution is trivial: Have 100 stock products, each of which exactly matches one of the 100 item sizes. This solution is perfect in the sense that it has zero waste. An optimization model with the objective of minimizing waste should find this solution.
However, managing 100 stock products is not practical because it would make the manufacturing process too complex. In practice, we want only a few stock products.
We don't have an objective function that quantifies the trade-off between the number of products and the amount of trim waste that is acceptable. Instead, the trade-off is a qualitative aspect that the decision maker will consider. Consequently, our modelling task is to inform the decision making process by quantifying what we can. That is:
We want to use only a few stock products, say between 1 and 10.
For a given number of stock products, what sizes should they be to minimize weighted trim waste in the production of the items?
What is the trade-off between the number of stock products and the amount of weighted trim waste?
Note that a heuristic method has already been devised to find a good, though not optimal, solution for six stock products. We'll use the heuristic solution as a benchmark for comparison with our optimization modelling.
Example minimizing trim loss
To illustrate the situation, suppose we have only five items that we make in our manufacturing process, as shown in Figure 1. Each item is unique, with a variety of width and length sizes. The volume weights vary across the items. The data for this test case is available in the GitHub repository.
Figure 1. Item sizes (width x length)
If we have five stock products that exactly match the item sizes, then the trim waste would be zero. At the other extreme, if we have just one stock product, then it would need to be 500x500, leading to 96.6% trim loss – i.e., almost double the weighted item area.
What if we have, say, two stock products? The two stock product sizes that minimize the weighted trim loss are shown in Figure 2. We have one product to cover the three smaller items and one product to cover the two larger items.
Figure 2. Best two stock products
The dimensions of each stock product exactly match the maximum width and/or length of the items they are allocated to, as shown in Figure 3. The 3rd item from the left has zero trim, while the others must be trimmed along their width, length, or both. The total amount of trim is 37.6% (i.e., product area in excess of item area, weighted by the annual demand for each item). That is, increasing the number of stock products from one to two more than halved the amount of trim loss waste.
Figure 3. Trim loss for two stock products (items overlaid on stock products)
If we allow the stock items to be rotated by 90° before trimming (or, equivalently, rotate the stock products), then we can reduce the size of the larger product, as shown in Figure 4.
Figure 4. Best products, with rotation
That is, without rotation, we had to make the larger product 500x500 to cover the height of the 4th item and the width of the 5th item. But if we rotate the 4th item, then the stock product can be smaller. The result is shown in Figure 5. Now the 5th item has no trim, and the trim on the 4th item is noticeably smaller. This solution has weighted trim loss of 26.4% – a significant improvement compared with the solution without rotation.
Figure 5. Trim loss, with rotation
Analysis of the situation
A sample of the actual data is shown in Figure 6. There are 100 items, each of which has a width, length, and weight (which we can interpret as an annual order volume).
From looking at this data, and thinking about the situation, we make some observations:
Figure 6. Sample of item dataThe widths and lengths are integers that vary between 438mm and 1006mm.
Each combination of item width and length is unique, though some individual sizes appear multiple times. For example, five items have a width of 584mm, though each has a different length.
We want to minimize the amount of waste, which is proportional to the difference in areas between an item and the stock product it is cut from, summed over all items and weighted by the annual volumes.
We need to consider only product sizes that appear in the list of items. There is no point in having a product of size 600x800 applied to an item that is 564x762, as doing so would produce unnecessary trim waste.
Our manufacturing process allows the stock products to be rotated before trimming to produce the items. That is, we're indifferent between stock that is 564x962 and stock that is 962x564. Being able to rotate the stock may lead to less trim waste. We can mimic rotation by sorting the item sizes so that the width is always the longer side. This insight may not be obvious, so we'll return to it in a later article.
We will need binary variables to allocate stock products to items. If we treat the stock dimensions as variables, then the model will be non-linear with multiplication of variable terms like: Width x Length x Allocation. That may make the model difficult to solve.
Formulation for Model 1
In our first attempt at modelling the situation, we represent the situation essentially as it is presented. That is, we formulate the situation as a non-linear, mixed integer optimization model, with variables for the stock product widths and lengths, and variables for the allocation of items to stock products. All the variables are binary. The width and length variables select sizes from lists of the item widths and lengths respectively, since those are the only sizes that we need to consider.
We also must decide how many stock products to use. We could make that a variable, then let the model decide. But, as noted above, the optimal solution is to have the number of stock products equal the number of items (with dimensions to match). With 100 items, this trivial solution would have 100 stock products, which isn't practical. Therefore, we'll make the number of stock products exogenous, and then solve the model for a range of values. Since we want "only a few" stock products, we'll manually vary the number of stock products from 1 to 10. Deciding the best number of stock products is a qualitative judgement that we'll leave to the decision maker, informed by our quantitative modelling.
Key features of the formulation for Model 1, as shown in Figure 7, are:
Equation (1). Our objective is to minimize the trim loss, which is the weighted area of the stock products allocated to each item minus the weighted area of the items. In the output, we express this as a percentage increase over the weighted area of the items. An ideal solution has zero trim loss.
Equation (2) says that the width of an allocated stock product must be at least the width of each item it is allocated to.
Equation (3) is the same, except for the length.
Equation (4) says that each item has exactly one stock product allocated to it.
Equation (5) says that each stock product has exactly one width. Equation (6) says the same, except for the length.
Figure 7. Model 1 formulation
\begin{alignat}{1}
&\text{Objective}\\
&\quad \text{Minimize} \quad TrimWaste \quad &= &\quad \sum_{i=1}^m \sum_{s=1}^n \left( Allocation_{i, s} \times \text{Weight}_i \times Area \right) - \sum_{i=1}^m \text{Width}_i \times \text{Length}_i \times \text{Weight}_i \tag{1} \\
&\text{where}\\
&\quad Area &= &\quad \left( \sum_i \text{Width}_i \times SelectWidth_{i, s} \right) \times \left( \sum_i \text{Length}_i \times SelectLength_{i, s} \right)\\
\\
&\text{Subject to} \\
&\quad \text{Width}_i \quad &\le &\quad \sum_{s=1}^n \left[ Allocation_{i, s} \times \left( \sum_{i=1}^m \text{Width}_i \times SelectWidth_{i, s} \right) \right] \quad &\forall \ i \in I \tag{2}\\
&\quad \text{Length}_i \quad &\le &\quad \sum_{s=1}^n \left[ Allocation_{i, s} \times \left( \sum_{i=1}^m \text{Length}_i \times SelectLength_{i, s} \right) \right] \quad &\forall \ i \in I \tag{3}\\
&\quad \sum_{s=1}^n Allocation_{i, s} &= &\quad 1 \quad &\forall \ i \in I, \forall \ s \in S \tag{4}\\
&\quad \sum_{i=1}^m SelectWidth_{i, s} &= &\quad 1 \quad &\forall \ i \in I, \forall \ s \in S \tag{5}\\
&\quad \sum_{i=1}^m SelectLength_{i, s} &= &\quad 1 \quad &\forall \ i \in I, \forall \ s \in S \tag{6}\\
\\
&\text{Variables} \\
&\quad SelectWidth_i \quad &= &\quad \text{Select one of the item widths, binary} \quad &\forall \ i \in I \tag{7}\\
&\quad SelectLength_i \quad &= &\quad \text{Select one of the item lengths, binary} \quad &\forall \ i \in I \tag{8}\\
&\quad Allocation_{i, s} \quad &= &\quad \text{Allocate item to product, binary} \quad &\forall \ i \in I, \forall \ s \in S \tag{9}\\
\\
&\text{Data} \\
& \quad \text{Width}_i &= &\quad \text{Width of item} \quad &\forall \ i \in I \tag{10}\\
& \quad \text{Length}_i &= &\quad \text{Length of item} \quad &\forall \ i \in I \tag{11}\\
& \quad \text{Weight}_i &= &\quad \text{Weight of item} \quad &\forall \ i \in I \tag{12}\\
\\
&\text{Sets} \\
& \quad I &&\quad \text{Item} \tag{13} \\
& \quad S &&\quad \text{Stock product} \tag{14} \\
\\
&\text{Dimensions} \\
& \quad m &&\quad \text{Number of items} \tag{15} \\
& \quad n &&\quad \text{Number of stock products} \tag{16} \\
\end{alignat}
Implementation
We initially built a prototype model in Excel, to see if it would work. Using the Advanced version of OpenSolver, the Couenne solver quickly found optimal solutions on small test data (5 items). However, Couenne failed to find any feasible solutions on the full data, even after running for hours.
So, we built the model in Python, using the Pyomo library. This was for two reasons:
Pyomo can access a wider range of solvers.
We want to run the model for a range of stock product sizes, which is easier to do in Python.
Attempting to solve the Python Model 1 using Couenne produces an error. It is not clear why.
In any case, we specifically wanted to try solving the Python model using the Octeract global, non-linear solver, which is available on NEOS Server through Pyomo. Octeract quickly solves Model 1 with small test data and a small number of stock products. However, like Couenne, Octeract struggles with more than a few stock products and, on the full data, Octeract fails to find feasible solutions even after running for up to 8 hours.
Other solvers available from Pyomo also fail to solve Model 1 with the full data set. So, we use a Pyomo feature of writing the model to a file and then manually run that file on NEOS using its web interface. This allows us to try solvers that are available on NEOS but not available directly through the Pyomo interface.
This is, we write the model to a file using code like:
Pyomo infers the output format from the file name – in this case, it writes a GAMS file, which many of the solvers can read. We also have an option for using the symbols used to define the model – doing so makes the file easier to read, but much longer (which might matter for large models, given the file upload size limit imposed by NEOS Server).
Jupyter Notebooks
The Python model is built using Jupyter Notebooks, which we've previously used for many of our blog articles.
In this article series we'll be building several models, so we're using a modular approach. Specifically, we've divided the code into several notebooks, some of which will be shared across the models. The model notebook then consists only of a few lines of code, where we set some global assumptions and run the model, having imported the other notebooks into the model notebook like:
# Include other notebooks
%run ./components/imports.ipynb
%run ./components/utilities.ipynb
%run ./components/solver.ipynb
%run ./components/data-model-1.ipynb
%run ./components/formulation-model-1.ipynb
%run ./components/output-model-1.ipynb
%run ./components/main-model-1.ipynb
Each of the models has the same structure, with component notebooks being imported as required. This type of modular structure makes it much easier to manage the code.
In our article Refactor Python models into modules, we describe refactoring an existing model into modules. In that example we used external Python files, rather than notebooks, but the idea is essentially the same.
Solutions
We have some success using the BARON global, non-linear solver, run manually on NEOS. The best solutions we found, for cases with 2 to 10 stock products, are shown in Figure 8. For comparison, we also show a solution found via a heuristic method for 6 stock products. The "ideal" solution has 100 stock products, with trim loss of exactly zero – though that is not a practical solution acceptable to the decision maker.
The chart doesn't show the solution for 1 stock item, which can be calculated without the model, as it is especially inefficient – it has a trim loss of 53.4%.
We expect the solutions to have a declining weighted trim loss percentage as the number of stock products increases, curving down to zero at 100 stock products. That is, having two stock products is expected to be substantially better than having one product. Three products should be better than two stock products, though the improvement will be smaller. Having 100 stock products should be better than 99 stock products, but only by a very small amount (possibly zero).
Figure 8. Solutions for a range of stock product counts
The heuristic solution has a trim loss of 5.3% for 6 stock products. This is quite a good solution. BARON found a solution that has slightly higher trim loss.
BARON found optimal solutions for 1 and 2 stock products in a few minutes, while the other cases required 8 hours of run time to find feasible, though not optimal, solutions. Three of the BARON solutions for Model 1 are better than the heuristic – i.e., for 3, 4, and 5 stock products, with the 5-product solution having a trim loss of 3.7%. The Model 1 solutions for 7, 9, and 10 stock products are obviously poor, as we should be able to achieve better solutions with more stock products. Note that BARON failed to find a feasible solution for 8 stock products, even after running for 8 hours.
Next steps
With Model 1, we can find optimal solutions for small, test data. For the full data, with 100 items, Model 1 works OK for a small number of stock products (up to 5), for 6 stock products it finds a solution that is similar to the heuristic, and for a larger number of stock products Model 1 performs poorly.
Model 1 is non-linear, with multiplication of variables in the objective function and in the constraints. The formulation is mathematically awkward, so it is not surprising that the various solvers have difficulty finding optimal (or even feasible) solutions for the full data set.
It might be possible to define a non-linear formulation that is easier to solve. We did try an alternative formulation, with the width and length variables being the sizes rather than binary selections from lists. But that model's performance was worse than Model 1.
Where possible, the best approach is to define a linear model, as linear models are generally easier to solve. However, there's no guarantee that a linear model will perform satisfactorily, as it will still require binary variables. In the next article, we'll create a linear model for our trim loss minimization situation, to see if it performs better.
Conclusion
In this article we describe a model for minimizing the trim loss resulting from cutting stock products to the sizes we need. We can find a perfect optimal solution, with zero waste, without a model – but the resulting solution is not practical. Instead, we have both quantitative and qualitative objectives to consider in our analysis.
Model 1 is non-linear and, in most cases, difficult to solve. Even after a run time of 8 hours, many of the case solutions are far from optimal. We did find some good solutions but, overall, the results are not satisfactory. This position is common in modelling projects, where a first attempt at modelling the situation provides valuable insights but not a usable solution.
So, we need a better approach. In the next article, we'll create a linear model, which we hope will be easier to solve. All going well, a linear model will lead to better, perhaps optimal, solutions.
If you would like to know more about this model, or you want help with your own models, then please contact us.
References
This series of articles addresses a question asked on Reddit:
