| Order Width | Order Quantity |
|---|---|
| 20 | 100 |
| 30 | 120 |
| 40 | 40 |
| 50 | 20 |
12 The Cutting Stock Problem
The cutting stock problem (CSP) is a common problem in the paper industry, where large rolls of paper must be cut into smaller rolls of various widths to meet customer demands. For example, a paper mill may have a large roll of paper that is 60 inches wide and needs to produce smaller rolls of widths 30, 24, 18, and 12 inches. The mill must determine the best way to cut the large roll of paper into the required widths while minimizing waste.
Let’s say that a paper company produces rolls with a uniform width of 100 inches and receives orders for rolls with widths of 20, 30, 40, and 50 inches. Table 12.1 shows the order details.
To fulfill these orders, a single 100 inch roll can be cut into one or more of the order widths. This process generates scrap, which is the leftover material that cannot be used. The different combinations of cuts are called patterns. In this case, there are many possible patterns but for simplicity purpose, we’ll assume only the 10 patterns listed in Table 12.2 are available.
| Pattern | Width (20) | Wdith (30) | Width (40) | Width (50) |
|---|---|---|---|---|
| Pattern 1 | 1 | 1 | 1 | 0 |
| Pattern 2 | 1 | 1 | 0 | 1 |
| Pattern 3 | 0 | 0 | 1 | 1 |
| Pattern 4 | 3 | 0 | 1 | 0 |
| Pattern 5 | 0 | 2 | 1 | 0 |
| Pattern 6 | 0 | 0 | 0 | 2 |
| Pattern 7 | 5 | 0 | 0 | 0 |
| Pattern 8 | 0 | 3 | 0 | 0 |
| Pattern 9 | 0 | 0 | 2 | 0 |
| Pattern 10 | 2 | 0 | 0 | 1 |
The objective of the cutting stock problem is to reduce the amount of material wastage while fulfilling the specified demands. The demand for each order is denoted by \(r_i\), and the number of order size \(i\) in pattern \(j\) is represented by \(a_{ij}\). To achieve this objective, we introduce the variable \(x_j\) which is a non-negative integer representing the frequency with which pattern \(j\) is used to fulfill the orders. The index \(j\) ranges from 1 to 10. Thus, the problem can be expressed as follows.
\[\begin{align} \text{min.} &\quad \sum_{j = 1}^n x_j \label{cutting-obj} \\ \text{s.t.} &\quad \sum_{j=1}^n a_{ij} x_j \geq r_i, \ \forall i \in \mathcal{I} \label{cutting-cons1} \\ &\quad x_j \in \mathbb{Z}^{+}=\{1,2,3,\ldots\}, \ \forall j \in \{1, \cdots, 10\} \label{cutting-cons2} \end{align}\]
Now we solve this contrived cutting stock problem using OR-Tools. The code below gives the complete program.
from ortools.linear_solver import pywraplp
# prepare data
num_orders = 4
order_quantities = [100, 120, 40, 20]
num_patterns = 10
pattern_details = [
[1, 1, 1, 0],
[1, 1, 0, 1],
[0, 0, 1, 1],
[3, 0, 1, 0],
[0, 2, 1, 0],
[0, 0, 0, 2],
[5, 0, 0, 0],
[0, 3, 0, 0],
[0, 0, 2, 0],
[2, 0, 0, 1]
]
# instantiate solver
solver = pywraplp.Solver.CreateSolver('SCIP')
# create decision varaibles
infinity = solver.Infinity()
var_j = [
solver.IntVar(0, infinity, name=f'x_{j}')
for j in range(num_patterns)
]
# create objective function
solver.Minimize(solver.Sum(var_j))
# create constraints
for i in range(num_orders):
expr = [
var_j[j] * pattern_details[j][i]
for j in range(num_patterns)
]
solver.Add(solver.Sum(expr) >= order_quantities[i])
# solve the problem
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
obj = solver.Objective().Value()
print(f"optimal obj = {obj}")
opt_j = [
var_j[j].solution_value()
for j in range(num_patterns)
]
print(opt_j)optimal obj = 83.0
[0.0, 20.0, 0.0, 0.0, 40.0, 0.0, 16.0, 7.0, 0.0, 0.0]Table 12.3 shows the final quantities produced for every order width.
| Pattern | Width (20) | Wdith (30) | Width (40) | Width (50) | Optimal Quantity |
|---|---|---|---|---|---|
| Pattern 1 | 1 | 1 | 1 | 0 | 0 |
| Pattern 2 | 1 | 1 | 0 | 1 | 20 |
| Pattern 3 | 0 | 0 | 1 | 1 | 0 |
| Pattern 4 | 3 | 0 | 1 | 0 | 0 |
| Pattern 5 | 0 | 2 | 1 | 0 | 40 |
| Pattern 6 | 0 | 0 | 0 | 2 | 0 |
| Pattern 7 | 5 | 0 | 0 | 0 | 16 |
| Pattern 8 | 0 | 3 | 0 | 0 | 7 |
| Pattern 9 | 0 | 0 | 2 | 0 | 0 |
| Pattern 10 | 2 | 0 | 0 | 1 | 0 |
| Produced Order | 100 | 121 | 40 | 20 | 83 |
This example problem seems trivial to solve, but in practice the CSP is challenging to solve because of the large number of possible cutting patterns that can be used and the combinatorial nature of the problem.
To efficiently solve the cutting stock problem, a column generation approach is often used. The basic idea behind column generation is to start with a small subset of the possible cutting patterns, and then iteratively generate and add new cutting patterns to the problem until an optimal solution is found.
The column generation approach involves solving a master problem and a subproblem iteratively. The master problem involves selecting the best set of cutting patterns from a larger set of potential patterns, while the subproblem involves finding the next cutting pattern(s) to add to the master problem. By solving these two problems iteratively, the algorithm can gradually add new cutting patterns to the master problem until the optimal solution is reached.
The column generation approach has several advantages over other methods for solving the cutting stock problem. First, it can handle large-scale instances of the problem more efficiently. This is because the algorithm only considers a subset of the possible cutting patterns at each iteration, which reduces the computational time and memory required. Second, the approach is flexible and can easily handle changes in the problem parameters, such as demand or material availability. Finally, the approach is guaranteed to converge to an optimal solution, provided certain conditions are met.
Overall, the cutting stock problem is challenging to solve due to its combinatorial nature and large number of possible cutting patterns. The column generation approach is a powerful technique for solving this problem efficiently and effectively, and is widely used in practice.