The Cutting Stock Problem

The origin of the cutting stock problem is in the paper industry. Given paper rolls of fixed width and a set of orders for rolls of smaller widths, the objective of the Cutting Stock Problem is to determine how to cut the rolls into smaller widths to fulfill the orders in such a way as to minimize the amount of scrap.

Problem Statement

An Example (from Linear Programming by Vasek Chvatal, 1983)

Suppose that rolls are produced in a uniform width of 100 inches and that orders can be placed for rolls of widths 14 inches, 31 inches, 36 inches, and 45 inches. The company has received the following orders:
$\begin{array}{|c|c|} \text{Order Width} & \text{Quantity Ordered} \\ \hline 14 & 211 \\ 31 & 395 \\ 36 & 610 \\ 45 & 97 \end{array}$

A single 100 inch roll can be cut into one or more of the order widths. For example, one roll could be cut into two rolls of 45 inches with a 10 inch roll of scrap.

Or a roll could be cut into a roll of 45 inches, a roll of 31 inches, and a roll of 14 inches with no scrap. Each such possible combination is called a pattern. For this example, there are 37 different patterns. Determining how many of each pattern to cut to satisfy the customer orders while minimizing the scrap is too difficult to do by hand. Instead the problem can be formulated as an optimization problem, specifically an integer linear program.

Mathematical Formulation

Sets
$$I$$ = set of order widths
$$J$$ = set of patterns

Parameters
$$a_{ij}$$ = number of rolls of width $$i$$ cut in pattern $$j$$
$$b_i$$ = demand for order width $$i$$

Decision Variables
$$x_j$$ = number of rolls cut using pattern $$j$$

The objective of the cutting stock problem is to minimize the number of rolls cut subject to cutting enough rolls to satisfy the customer orders. Using the notation above, the problem can be formulated as follows:

Minimize $$\sum_{j \in J} x_j$$
subject to $$\sum_{j \in J} a_{ij} x_j \geq b_i, \forall i \in I$$
$$x_j$$ integer

Solution Approach

The cutting stock problem is an integer linear program with one integer decision variable for each possible pattern. If the number of order widths is small, then the number of patterns may be small enough that the problem can be solved using a standard branch-and-bound algorithm. However, if the number of order widths is large, then there may be an exponential number of patterns, too many for the problem to be solved efficiently using a standard branch-and-bound algorithm. In fact, there may be too many patterns even to write the complete set. In these cases, an alternative solution approach is needed.

Delayed column generation approach

The motivation for the delayed column generation approach is the observation that it is not necessary to generate the complete set of patterns prior to solving the problem. Instead, the problem can be solved using an iterative process, starting with a small number of patterns and generating additional patterns as needed. A separate optimization problem, the knapsack problem, is solved to identify new patterns to add. The delayed column generation approach includes the following steps.

1. Select an initial set of patterns.
2. Solve the linear programming relaxation of the cutting stock problem. That is, relax the $$x_j$$ integer restriction to be $$x_j \geq 0$$ in the mathematical formulation specified above and solve the resulting linear program.
3. Use the dual prices from the linear programming relaxation solution to solve a knapsack problem. Let $$y_i$$ be the dual variable corresponding to constraint $$i$$ in the linear programming relaxation, let $$w_i$$ be the width of order width $$i$$, and let $$L$$ be the uniform width of the rolls. Let $$z_i$$ be an integer variable representing the number of rolls of order width $$i$$ to cut from a roll. Then, the problem of generating new patterns can be formulated as the following knapsack problem:
Maximize $$Z = \sum_{i \in I} y_i z_i$$

subject to $$\sum_{i \in I} w_i z_i \leq L$$

$$z_i$$ integer

The knapsack problem can be solved using a variety of methods. If the optimal objective value $$Z \geq 1$$, then the values of the integer variables $$z_i$$ specify the number of rolls of order width $$i$$ in the new pattern. Add the new pattern and go to step 2. Otherwise, the linear programming relaxation solution (of the cutting stock problem) is optimal.

4. If the linear programming relaxation solution is integer, then stop. Otherwise, use an advanced algorithm to obtain an integer solution.

AMPL Model


#____________________________
#CUTTING STOCK USING PATTERNS
#____________________________

param roll_width >0;

set WIDTHS;
param orders {WIDTHS} >0;

param nPAT integer >=0;
set PATTERNS := 1..nPAT;

param nbr {WIDTHS, PATTERNS} integer >=0;

check {j in PATTERNS}:
sum {i in WIDTHS} i*nbr[i,j] <=roll_width; var Cut {PATTERNS} integer>=0;

minimize Number:
sum {j in PATTERNS} Cut[j];

subj to Fill {i in WIDTHS}:
sum {j in PATTERNS} nbr[i,j] * Cut [j] >=orders[i];

#______________________________________
#KNACKSACK SUBPROLEM FOR CUTTING STOCK
#______________________________________

param price {WIDTHS} default 0.0;

var Use {WIDTHS} integer >=0;

minimize Reduced_Cost:
1 - sum {i in WIDTHS} price[i] * Use[i];

subj to Width_Limit:
sum {i in WIDTHS} i * Use[i] <= roll_width; #__________________________ #GILMORE-GOMORY METHOD FOR #CUTTING STOCK PROBLEM #__________________________ #option solver cplex; option solver osl; option solution_round 6; option display_1col 1000; model cut.mod; data cut.dat; problem Cutting_Opt: Cut, Number, Fill; option relax_integrality 1; problem Pattern_Gen: Use, Reduced_Cost, Width_Limit; option relax_integrality 0; let nPAT :="0;" for {i in WIDTHS} { let nPAT :="nPAT" +1; let nbr[i,nPAT] :="floor" (roll_width/i); let {i2 in WIDTHS: i2 <> i} nbr[i2,nPAT] :=0;
};

repeat {
solve Cutting_Opt;

let {i in WIDTHS} price[i] := Fill[i].dual;

solve Pattern_Gen;

if Reduced_Cost <-0.00001 then { let nPAT :="nPAT" +1; let {i in WIDTHS} nbr[i,nPAT] :="Use[i];" } else break; }; option display_width 100; display nbr>nbr.results;
display Cut >cut_decimal.results;

option Cutting_Opt.relax_integrality 0;
solve Cutting_Opt;

display Cut >cut.results;