🧩 Constraint Solving POTD:Cutting Stock Problem — 1D Trim Loss Minimization

[github-actions[bot]]

Category: Packing & Cutting | Date: 2026-04-14

The Cutting Stock Problem (CSP) is one of the oldest and most practically important problems in operations research. Despite its deceivingly simple description, it sits at the intersection of combinatorial optimization, integer programming, and constraint programming — and it gave birth to one of the most influential algorithmic ideas in OR: column generation.

---

Problem Statement

A paper mill produces rolls of a fixed width W = 100 cm. Customers order pieces of smaller widths. Given a set of demand orders, cut the stock rolls to satisfy all demands while minimizing the total number of rolls used (equivalently, minimizing waste/trim loss).

Concrete Instance

Order	Width (cm)	Demand (pieces)
1	45	3
2	36	5
3	31	7
4	14	12

Stock roll width: W = 100 cm

A cutting pattern specifies how many pieces of each width to cut from a single roll. For example:

• Pattern A: [1×45, 1×36, 0×31, 1×14] → uses 95 cm, wastes 5 cm ✓
• Pattern B: [0×45, 0×36, 3×31, 0×14] → uses 93 cm, wastes 7 cm ✓
• Pattern C: [2×45, 0×36, 0×31, 0×14] → uses 90 cm, wastes 10 cm ✓

Goal: Choose how many times to use each feasible pattern so all demands are met with the fewest rolls.

---

Why It Matters

Paper, steel, glass, and textile industries use cutting stock daily to reduce material waste, directly impacting cost and sustainability. A 1% reduction in trim loss across a large mill can translate to millions of dollars annually.

Lumber and wood panel production uses 2D generalizations of this problem (guillotine cutting), where minimizing offcuts is critical for high-value materials like hardwoods.

Semiconductor wafer dicing and printed circuit board panelization are modern variants, where the "stock" is a wafer or panel and pieces are chips or PCBs.

---

Modeling Approaches

Approach 1: Column Generation (MIP / LP Relaxation)

The classical Gilmore-Gomory formulation uses patterns as columns in an LP.

Decision variables: x_j ≥ 0 — number of times pattern j is used
Parameters: a_ij — number of pieces of order i cut in pattern j

Minimize   Σ_j  x_j
Subject to:
  Σ_j a_ij · x_j  ≥  d_i    for all orders i   (demand coverage)
  Σ_i w_i · a_ij  ≤  W      for all patterns j  (pattern feasibility)
  x_j ∈ Z+                                      (integer cuts)
```

**The challenge**: there are exponentially many feasible patterns. Column generation solves the LP relaxation iteratively:
1. Start with a small set of initial patterns.
2. Solve the LP (master problem).
3. Find the most promising new pattern by solving a **pricing subproblem** (a knapsack problem using the dual prices).
4. Add the new pattern and repeat until no improving column exists.

**Trade-offs**: The LP relaxation is tight (often within 1 of optimal), but the final rounding to integers can be tricky. Branch-and-price extends this to exact integer solutions.

#### Approach 2: CP / CSP Formulation

Model patterns explicitly as a constraint satisfaction problem over a bounded number of rolls `N`.

**Decision variables**:
- `pattern[r][i]` ∈ `{0..⌊W/w_i⌋}` — pieces of order `i` cut from roll `r`
- `used[r]` ∈ `{0,1}` — whether roll `r` is used

**Constraints**:
```
For each roll r:
  Σ_i w_i · pattern[r][i]  ≤  W              (capacity)
  used[r] = 1  ⟺  Σ_i pattern[r][i] > 0      (used flag)

For each order i:
  Σ_r pattern[r][i]  ≥  d_i                   (demand)

Symmetry breaking:
  used[1] ≥ used[2] ≥ ... ≥ used[N]            (roll ordering)

Objective: Minimize Σ_r used[r]

Trade-offs: CP models are more expressive and easier to add side constraints (e.g., color changes, setup costs), but the LP-based column generation approach typically scales much better on large industrial instances.

Example Model (MiniZinc)

int: W = 100;                        % stock width
int: n = 4;                          % number of order types
int: max_rolls = 15;                 % upper bound on rolls needed

array[1..n] of int: widths  = [45, 36, 31, 14];
array[1..n] of int: demands = [ 3,  5,  7, 12];

% pattern[r,i] = pieces of order i cut from roll r
array[1..max_rolls, 1..n] of var 0..10: pattern;

% used[r] = 1 if roll r is used at all
array[1..max_rolls] of var 0..1: used;

% Capacity constraint per roll
constraint forall(r in 1..max_rolls)(
  sum(i in 1..n)(widths[i] * pattern[r,i]) <= W
);

% Link used flag
constraint forall(r in 1..max_rolls)(
  used[r] = (sum(i in 1..n)(pattern[r,i]) > 0)
);

% Demand satisfaction
constraint forall(i in 1..n)(
  sum(r in 1..max_rolls)(pattern[r,i]) >= demands[i]
);

% Symmetry breaking: pack rolls in order
constraint forall(r in 1..max_rolls-1)(used[r] >= used[r+1]);

solve minimize sum(r in 1..max_rolls)(used[r]);

---

Key Techniques

1. Column Generation & Knapsack Pricing

The pricing subproblem — "find the pattern with the best reduced cost" — is a 0-1 knapsack or bounded knapsack problem. Since knapsack is NP-hard in general but fast in practice (pseudo-polynomial DP), this is feasible to solve repeatedly in the CG loop. The elegance here is that CP and DP naturally complement LP-based decomposition.

2. Symmetry Breaking

Cutting stock models suffer from permutation symmetry: any permutation of roll assignments gives an equivalent solution. The CP model above breaks this with a used[r] ≥ used[r+1] ordering constraint. More powerful symmetry breaking uses lex-leader constraints or value symmetry breaking (ensuring identical patterns are ordered consistently), which can dramatically prune the search tree.

3. Bin-Packing Bound & Dual Feasible Functions

A key lower bound comes from the LP relaxation's optimal value (the fractional optimum). Another classical bound uses dual feasible functions (DFFs): functions f: [0,W] → [0,1] that preserve feasibility of patterns. By choosing f cleverly (e.g., the FFD-based DFF), you can derive tight lower bounds without solving the LP — extremely useful in branch-and-bound.

---

Challenge Corner

Can you model the 2D version (rectangular cutting stock) as a CP problem?

In the 2D case, each order is a w_i × h_i rectangle, and the stock sheet is W × H. Feasibility requires non-overlapping placement, which is naturally captured by the diffn global constraint in CP.

• How would you adapt the column generation approach? (Hint: the pricing subproblem becomes a 2D strip packing problem — much harder!)
• Guillotine cuts restrict patterns to be produced by recursive horizontal/vertical cuts. Can you model this restriction efficiently?
• For the 1D problem: what happens to solution quality if demands d_i are not fixed but lie in ranges [d_i^min, d_i^max] (over-production is allowed)? How does this change the model?

---

References

1. Gilmore, P.C. & Gomory, R.E. (1961). "A Linear Programming Approach to the Cutting-Stock Problem." Operations Research 9(6):849–859. — The foundational paper introducing column generation for this problem.

2. Vance, P.H. (1998). "Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem." Computational Optimization and Applications 9(3):211–228. — Exact methods combining LP relaxation with branch-and-bound.

3. Wäscher, G., Haußner, H. & Schumann, H. (2007). "An Improved Typology of Cutting and Packing Problems." European Journal of Operational Research 183(3):1109–1130. — Comprehensive taxonomy of cutting/packing variants.

4. Clautiaux, F., Sadykov, R., Vanderbeck, F. & Viaud, Q. (2019). "Pattern-Based Diving Heuristics for a Two-Dimensional Guillotine Cutting-Stock Problem with Variable-Sized Stock." EURO Journal on Computational Optimization 7(3):247–278. — Modern treatment linking 1D theory to practical 2D applications.

Generated by Constraint Solving — Problem of the Day · ● 363.6K · ◷

• expires on Apr 21, 2026, 12:56 PM UTC

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #26423.