Cutting Stock Problem

Problem Description

A paper mill receives orders for rolls of paper of varying widths. The mill produces large master rolls of a fixed width $W$. Each master roll must be cut into smaller rolls to fill a set of orders. The goal is to minimise the number of master rolls used (equivalently, to minimise waste) while satisfying all orders.

Notation (all symbols defined here, before first use):

$W$

Width of a master roll.

$n$

Number of distinct order widths.

$w_i$

Width of order $i$, for $i = 1, \ldots, n$.

$d_i$

Demand (number of rolls required) for order $i$.

$a_{ij}$

Number of rolls of width $w_i$ produced by cutting pattern $j$.

$x_j$

Number of times cutting pattern $j$ is used.

$m$

Number of feasible cutting patterns (exponentially large).

A cutting pattern is a feasible assignment of widths to a master roll:

$\sum_{i=1}^{n} w_i a_{ij} \le W, \quad a_{ij} \in \mathbb{Z}_{\ge 0}$.

Block-Angular LP Formulation

The cutting stock problem can be stated as:

The LP relaxation sets $x_j \ge 0$ (replacing integrality). Because there are exponentially many patterns $m$, this LP cannot be solved by enumerating all columns — Dantzig-Wolfe Decomposition via column generation is the key technique.

Dantzig-Wolfe Master Problem

Introduce dual variables $\pi_i \ge 0$ for each demand constraint. The restricted master problem (RMP) maintains only a subset of columns $J \subseteq \{1, \ldots, m\}$:

At each iteration, solve the RMP and obtain dual variables $\pi_i^*$.

Role of dual variables: $\pi_i^*$ is the shadow price of demand $i$ — the marginal reduction in total rolls used if demand $i$ were increased by one unit. These prices drive the column generation sub-problem.

Pricing Sub-Problem (Knapsack)

Check whether any currently unlisted pattern can improve the objective. The reduced cost of a new pattern $a = (a_1, \ldots, a_n)^T$ is:

We seek a pattern with negative reduced cost — i.e., one that reduces total rolls. This is equivalent to solving a 0-1 knapsack problem:

If $\max \sum_i \pi_i^* a_i > 1$, a new improving column exists and is added to the RMP. Otherwise, the RMP is optimal.

Numerical Iteration (Example)

Consider $n = 2$ order widths, $W = 10$, $w_1 = 4$, $w_2 = 3$, $d_1 = 3$, $d_2 = 5$.

Initial patterns: Let $p_1 = (2, 0)^T$ (two rolls of width 4) and $p_2 = (0, 3)^T$ (three rolls of width 3).

Iteration 1:

• Solve RMP with $\{p_1, p_2\}$.
• Obtain duals $\pi_1^* = 0.5$, $\pi_2^* = 0.333$.
• Knapsack: maximise $0.5 a_1 + 0.333 a_2$ subject to $4a_1 + 3a_2 \le 10$.
• Optimal solution: $a_1 = 1, a_2 = 2$ giving value $0.5 + 0.667 = 1.167 > 1$.
• Add new pattern $p_3 = (1, 2)^T$.

Iteration 2:

• Re-solve RMP with $\{p_1, p_2, p_3\}$.
• Updated duals and check knapsack again.
• If no pattern achieves reduced cost $< 0$, LP is optimal.

Citation