Solver Max - One-dimensional packing: Wire cutting

15 February 2021

"Wire cutting" is a common type of production problem. That is, given available stock of wire (or other one-dimensional stock material) and a list of pieces required, what is the best way to cut the stock to fulfil the requirements while minimizing waste?

The benefits from improved cutting can be substantial, while poor cutting choices can be expensive. To illustrate how an optimization model can help us make the decision, in this article we design, build, and solve a wire cutting problem using OpenSolver.

Download the models

The model is available on GitHub.

Situation

We operate a manufacturing business. Our process involves cutting wire stock into pieces of specific lengths required to fulfil a customer order.

A standard item of wire stock is 10 metres (10,000 millimetres) long, though we also have available off-cuts from previous orders.

Our objective is to minimize the amount of wire wasted due to the cutting process. Therefore, we want to find a combination of the required piece lengths that are as close as possible to the stock lengths – potentially including the available off-cuts, where possible.

Model design

Potential modelling approaches

This situation is a variant of the more general class of situations known as packing problems. In this case, we treat the wire as being one-dimensional. Packing problems also encompass two-dimensional (e.g. pallet packing) and three-dimensional (e.g. box packing) situations.

Packing problems are often very difficult to solve optimally. In many situations, heuristics are used to find a good, rather than optimal, solution. In this situation, we're able to formulate an optimization model to solve our manufacturing problem.

Cutting requirements

Figure 1 shows an example list of wire piece lengths ordered by a customer. The lengths are expressed in millimetres (mm).

Our first observation is that the total length is just over 15 metres. Therefore, we'll need at least two new 10 metre stock lengths, or up to several off-cuts, to fulfil the customer order. To accommodate this situation, we'll need to design the model so that it can choose from several new stock and/or off-cut items.

Define the meaning of waste

Our objective is to minimize the amount of off-cut waste. But what does that mean, exactly?

For example, if we cut a 4,000 mm piece from a new 10,000 mm stock item, then is the 6,000 mm off-cut treated as waste? Of course not – such a long off-cut will be useful for later customer orders.

One way to handle this issue is to designate one stock item as a special case, where we don't include its off-cut in the objective function. This creates an incentive for the solver to put as much waste as possible into that stock item, as that waste isn't counted, rather than incurring waste in the stock items that are counted. As a consequence, the off-cut from that stock item is more likely to be long enough to be useful for later customer orders. This approach will work best if the special stock item is as long as possible, i.e. a new stock item.

Therefore, to give us some control over the solution process, we include a switch that specifies whether or not to include stock item 1 in the waste calculation. That is:

TRUE. The model treats all available stock items equally. With this setting, the model will find the global minimum waste, though the solution may not be ideal in practice.
FALSE. The model excludes stock item 1 from the waste calculation.

Must use off-cuts

In general, it is likely that the model will find it easier to fit several required pieces into a long new stock item rather than a shorter off-cut. This is likely to result in the use of more new stock items and not much use of the off-cuts. But we don't want many off-cuts accumulating over time, so that result would not be ideal.

Instead, it may be useful to have an option that enables us to direct the model towards particular off-cut stock items. This will help us to reduce the accumulation of off-cuts over time.

Therefore, we have a "must use" indicator for each stock item. This requires the model to use that stock item, then find the best cuts given those (and potentially other) stock items.

Model formulation

Our model formulation is shown in Figure 2.

That is:

Equation (1). We want to minimize the total length of off-cut waste from cutting the required pieces, with an option to exclude the waste from stock item 1.
Equation (2). An off-cut is defined as the remaining length of a stock item after cutting pieces from it.
Equation (3). The off-cut length must be physically possible.
Equation (4). We cut each required piece exactly once.
Equation (5). Cut pieces from a stock item only if we are using that item.
Equation (6). Must use specific stock items.

Figure 2. Mathematical formulation

\begin{alignat*}{1} &\text{Objective} \\ & \quad \text{Min } fOffcutWaste \quad &= &\quad \left ( \text{dUseOne} \times fOffCut_{s=1} \right )\\ &&&\quad + \sum_{s=2}^n fOffcut_{s} \tag{1} \\ & \quad \text{where } fOffcut_{s} \quad &= &\quad \left (vUseStock_{s} \times \text{dLength}_{s} \right )\\ &&&\quad - \sum_{p=1}^m \left ( \text{dPieces}_{p} \times vCuts_{p,s} \right ) \tag{2} \\ \\ &\text{Subject to} \\ & \quad fOffcut_{s} \quad &\ge &\quad 0 \quad &\forall \ s \in S \tag{3}\\ & \quad \sum_{s=1}^n vCuts_{p,s} \quad &= &\quad 1 \quad &\forall \ p \in P \tag{4}\\ & \quad vCuts_{p,s} \quad &\le &\quad vUseStock_{s} \quad &\forall \ p \in P, \forall \ s \in S \tag{5}\\ & \quad vUseStock_{s} \quad &\ge &\quad \text{dMustUse}_{s} \quad &\forall \ s \in S \tag{6}\\ \\ &\text{Variables} \\ & \quad vCuts_{p,s} &= &\quad \begin{cases} 1, &\text{if piece \(p\) is cut from stock \(s\)} \\ 0, &\text{otherwise} \tag{7} \end{cases} \quad &\forall \ p \in P, \forall \ s \in S \\ & \quad vUseStock_{s} &= &\quad \begin{cases} 1, &\text{if stock \(s\) is used} \\ 0, &\text{otherwise} \tag{8} \end{cases} \quad &\forall \ s \in S \\ \\ &\text{Data} \\ & \quad \text{dUseOne} &= &\quad \begin{cases} 1, &\text{if stock \(s=1\) is included in waste} \\ 0, &\text{otherwise} \tag{9} \end{cases} \\ & \quad \text{dLengths}_{s} &= &\quad \text{Length of each stock item} \quad &\forall \ s \in S \tag{10}\\ & \quad \text{dPieces}_{p} &= &\quad \text{Lengths of each piece required} \quad &\forall \ p \in P \\ \tag{11}\\ & \quad \text{dMustUse}_{s} &= &\quad \begin{cases} 1, &\text{if stock \(s\) must be used} \\ 0, &\text{otherwise} \tag{12} \end{cases} \quad &\forall \ s \in S \\ \\ &\text{Sets} \\ & \quad P &\ &\quad \text{Piece required} \tag{13} \\ & \quad S &\ &\quad \text{Stock item} \tag{14} \\ \\ &\text{Dimensions} \\ & \quad m &\ &\quad \text{Number of pieces required} \tag{15} \\ & \quad n &\ &\quad \text{Number of stock items available} \tag{16} \\ \\ &\text{Bounds} \\ & \quad \text{Non-negative} &\ &\quad \tag{17} \\ \end{alignat*}

Implementation

Specify the available stock

In addition to the piece lengths required by the customer, we need to tell the model what stock lengths are available. This is done in Figure 3, where we make four stock items available – a new stock item in position 1, and three off-cuts of various lengths. We also have a binary variable that indicates if a particular item must be used (1) or not (0).

As a simple check, we need to ensure that the total length of stock available is greater than or equal to the length of required pieces. If it is not, then there is no feasible solution.

But note that even if the total stock available is longer than the total required pieces, there is no guarantee that a feasible solution exists. In this example, our total available length of 20,130 mm is probably sufficient to fulfill the 15,200 mm length required by the customer. But we'll need to solve the model to be sure.

Allocate required pieces to stock items

The core of our model is allocating required pieces to stock items. This is done using the matrix shown in Figure 4.

We use a binary variable to indicate which stock item each required piece is cut from. Each piece is required only once, so the sum of each row must equal 1. Conversely, we may cut a stock item into several pieces – as indicated by the column totals.

Tie together the stock must use and cut variables

We have an additional set of binary variables that indicate if a stock item is used. These variables tie the stock must use indicator to the cut variables, by requiring that the cut variables are less than or equal to the use variables and the stock item must use variables are less than or equal to the stock use variables.

Solver model

Objective function

The Solver model is shown in Figure 5. Our objective is to minimize fOffcutWaste. The formula for calculating the off-cut waste includes a switch for whether or not to include stock item 1 in the waste calculation.

An alternative objective might be to minimize the number of stock items used. We could do that by setting the objective to be the sum of the vUseStock variables.

Variables

The model has two sets of variables:

vCuts. These are binary variables that indicate which required piece is cut from what stock item.
vUseStock. These binary variables indicate if a stock item is used.

Constraints

The constraints are:

fOffcut >= 0. This ensures that the off-cut length is physically possible.
fTotalCuts = 1. This implements the requirement that each required piece is cut from exactly one stock item.
vCuts <= fUsageMap. This maps the vUseStock variables to each element of the vCuts variable matrix.
vCuts = binary. Define cuts as a binary choice.
vUseStock = binary. Binary choice about which stock items to use.
vUseStock >= dMustUse. This links our input of must use stock to the cuts made.

Solution method

All of the model's relationships are linear, so we can use the Simplex method.

This model is sufficiently small that either Solver or OpenSolver can be used. We prefer to use OpenSolver for this model, as it is significantly faster – an advantage that becomes substantial if we expand the model to include more required pieces and/or stock items.

Analysis

Optimal solution

Figure 6. Initial optimal solution: Scenario A

We start with the default assumptions of no must use stock items and including stock item 1's off-cut in the total (i.e. the "Include stock 1 in waste calculation" assumption is set to TRUE).

Given our data and assumptions, a summary of OpenSolver's optimal solution is shown in Figure 6.

In the spreadsheet, on the Analysis sheet, this solution is referred to as Scenario A. We suggest that, before continuing, you replicate this solution in the model. In particular, understand how the variables and constraints interact to produce this solution.

Although this solution is optimal, it isn't actually very good. Specifically:

We used only two stock items, which is OK.
Stock item 1 has a 1,200 mm off-cut. This is sufficiently long that it will be useful for future customers, so that is also OK.
But the off-cut from stock item 2 is 280 mm. This is shorter than the length that customers typically order, so it is unlikely to be useful. Consequently, this solution is quite wasteful.

Alternative optima

Figure 7. Alternative optimal solution: Scenario B

Perhaps we can do better. In our model design, we included a switch to specify whether or not to count stock item 1's off-cut in the objective function. The result of setting that switch to FALSE, and re-solving, is shown in Figure 7.

The total off-cut is still 1,480 mm, so this is an alternative optima – meaning that the solver is indifferent between this solution and the previous one.

We now have all the off-cut allocated to stock item 1, which remains a good (and slightly larger) size for future use. But, importantly, stock item 2 now has zero waste, which is excellent.

Although the solver is indifferent between Scenarios A and B, we prefer this solution to the previous one.

Exploring other solutions

In Scenario B we achieved, effectively, zero waste. A natural follow-up question is: Can we achieve zero effective waste while also using stock items 3 and 4?

Figure 8. Other solutions: Scenarios C, D, and E

To answer this question, Figure 8 shows the results for three additional scenarios:

Top, Scenario C. We specify a requirement to use stock item 3. Since stock item 3 is relatively short, the solver must also use stock items 1 and 2 to fulfill the required pieces. This solution uses all of stock items 2 and 3 exactly, with zero waste. This is an excellent solution, even better than Scenario B.
Middle, Scenario D. We specify that stock item 4 must be used. The solver can't find a solution that exactly uses any of the stock items. Instead, the result is a small amount of off-cut from stock items 2 and 4. These off-cuts are too small to be useful, so they are actually waste.
Bottom, Scenario E. We specify that stock items 3 and 4 must be used. The solver uses all four stock items to fulfill the requirements. The result is small off-cut lengths from each of stock items 2, 3, and 4. The total waste is higher than for Scenario D.

Having explored a variety of potential solutions, we select Scenario C as the best because:

The solution fulfills the customer's requirements.
We used two existing off-cut stock items, with zero waste.
Stock items 1 and 4 remain as useful lengths for future orders.

Conclusion

This model is a simple example of solving a wire cutting problem in Excel.

Our model also demonstrates that it is important to explore the model's behavior, rather than just accepting the first result. Often, as in this example, there are alternative solutions that better meet our needs.

This outcome reinforces important general points about modelling: