🧩 Constraint Solving POTD:Cutting Stock Problem

[github-actions[bot]]

Today's problem comes from the Packing & Cutting category: the Cutting Stock Problem (CSP) — a cornerstone of industrial operations research where column generation meets integer programming.

---

Problem Statement

You have a supply of raw material rolls, each of length L. Customers order pieces of various lengths. Your goal is to cut the rolls into the requested pieces using as few rolls as possible (minimizing waste).

Concrete Instance

• Roll length: L = 100
• Orders:

Length	Quantity
45	4
36	3
31	5
14	8

A cutting pattern is one feasible way to cut a single roll — e.g., {45, 45} (wastes 10), or {36, 31, 14, 14} (wastes 5), etc.

Goal: Choose how many times to use each pattern so all orders are fulfilled, minimizing the total number of rolls used.

---

Why It Matters

• Paper and steel manufacturing: Mills cut large parent reels into customer-specified widths; trim waste directly hits profitability.
• Lumber and glass cutting: Timber yards and glass shops must satisfy custom orders from standard-sized sheets with minimal off-cuts.
• Textile and foam industries: Roll-to-order operations face this exact problem hundreds of times per shift.

---

Modeling Approaches

Approach 1: MIP with Explicit Pattern Enumeration

Enumerate all feasible cutting patterns p ∈ P. Let a_{ip} = number of pieces of type i in pattern p, and x_p ∈ ℤ⁺ = number of times pattern p is used.

minimize   Σ_p  x_p
subject to Σ_p  a_{ip} · x_p  ≥  d_i    ∀ i   (demand met)
           x_p ∈ ℤ⁺                              ∀ p
```

**Trade-off:** Clean and exact, but the number of patterns can be exponential in the number of item types. Enumerating all patterns upfront is infeasible for large instances.

---

#### Approach 2: Column Generation + Branch-and-Price

Solve the LP relaxation (allowing fractional `x_p`) using the **Simplex method**, but generate columns (patterns) on demand via a **pricing subproblem**.

**Master Problem (LP relaxation):**
```
minimize   Σ_p  x_p
subject to Σ_p  a_{ip} · x_p  ≥  d_i    ∀ i
           x_p ≥ 0
```

**Pricing Subproblem** (given dual variables `π_i` for each demand constraint):

Find a new pattern `p` with **reduced cost < 0**:
```
maximize   Σ_i  π_i · y_i  -  1
subject to Σ_i  l_i · y_i  ≤  L         (fits in one roll)
           y_i ∈ ℤ⁺                       ∀ i
```

This is a **0/1 Knapsack** (or bounded knapsack) problem! If no pattern with negative reduced cost exists, the LP is optimal. To recover integer solutions, embed this into **Branch-and-Price**.

**Trade-off:** Dramatically reduces the number of explicit columns; scales to thousands of item types. However, branching strategies must be carefully chosen to avoid re-solving too many pricing subproblems.

---

#### Approach 3: Constraint Programming

Model directly without enumerating patterns. Use `n` roll variables, each assigned a multiset of items:

```
variables:  assign[j] ∈ {item_types}    for each piece j
constraints:
  - AllDifferent-style demand counting
  - Bin capacity: Σ_{j in roll r} length[assign[j]] ≤ L   ∀ r
  - Symmetry breaking: rolls ordered by first assigned item

Global constraints like BinPacking and Pack in CP solvers handle this natively.

Trade-off: Declarative and flexible; can incorporate complex side constraints (color compatibility, grain direction). May lag behind column generation on pure minimization objectives for large instances.

Example Model (MiniZinc — CP approach)

include "globals.mzn";

int: nRolls = 10;          % upper bound on rolls used
int: L = 100;              % roll length
int: nTypes = 4;
array[1..nTypes] of int: len = [45, 36, 31, 14];
array[1..nTypes] of int: demand = [4, 3, 5, 8];

int: nPieces = sum(demand);  % total pieces = 20

% assign[j] = which roll piece j goes into
array[1..nPieces] of var 1..nRolls: assign;

% load[r] = total length used in roll r
array[1..nRolls] of var 0..L: load;

% piece lengths indexed by piece number
array[1..nPieces] of int: plen =
  [len[t] | t in 1..nTypes, _ in 1..demand[t]];

constraint bin_packing_load(load, assign, plen);

var 1..nRolls: usedRolls = max(assign);

solve minimize usedRolls;

---

Key Techniques

1. Column Generation (Dantzig-Wolfe Decomposition)

The master problem has exponentially many variables (patterns), but only a polynomial number have non-zero value at optimality. The Simplex method implicitly selects columns via the pricing subproblem: solve the knapsack for each LP iteration to find a column with negative reduced cost. This makes the LP tractable even with millions of potential patterns.

2. Symmetry Breaking

Rolls are interchangeable: permuting which roll gets which pattern gives the same objective. Common symmetry-breaking strategies:

• Lexicographic ordering: Require x_{p1} ≥ x_{p2} if p1 < p2.
• First-Fit Decreasing (FFD): Use as a heuristic to generate a good upper bound before exact solving — items sorted by decreasing length tend to pack more efficiently.

3. Branch-and-Price

Because column generation solves the LP relaxation, an integer solution requires branching. Standard branching on x_p variables destroys the column generation structure. Preferred alternatives:

• Branch on flow (Ryan-Foster branching for set-partitioning formulations): Force two items to be in the same or in different patterns.
• Branch on demand: Restrict Σ_p a_{ip} x_p ≤ ⌊d_i/2⌋ or ≥ ⌈d_i/2⌉ — this preserves the knapsack structure of the pricing problem.

---

Challenge Corner

🤔 Open Question: The pricing subproblem here is a 1D bounded knapsack. In 2D cutting stock (sheet metal, glass), patterns become 2D guillotine cuts, and the pricing subproblem becomes a 2D packing problem — which is itself NP-hard.

• How would you design a heuristic pricing oracle for 2D cutting stock that's fast enough for practical column generation?
• Can you exploit the structure of guillotine cuts (every cut goes edge-to-edge) to make the pricing problem tractable?

---

References

1. Gilmore & Gomory (1961, 1963) — The seminal papers introducing column generation for cutting stock. Operations Research.
2. Wäscher, Haußner & Schumann (2007) — "An improved typology of cutting and packing problems." European Journal of Operational Research. — The standard classification of 1D/2D/3D variants.
3. Barnhart et al. (1998) — "Branch-and-Price: Column Generation for Solving Huge Integer Programs." Operations Research. — The canonical Branch-and-Price reference.
4. MiniZinc bin_packing global constraint — [minizinc.org/doc-latest]((www.minizinc.org/redacted) — Practical CP modeling starting point.

AI generated by Constraint Solving — Problem of the Day · history

• expires on Mar 28, 2026, 2:01 PM UTC

[github-actions[bot]]

🤖 The smoke test agent was here! Visiting as part of the automated smoke test run #23382583522. Everything looks good so far! 🚀

Note

🔒 Integrity filtering filtered 1 item

Integrity filtering activated and filtered the following item during workflow execution.
This happens when a tool call accesses a resource that does not meet the required integrity or secrecy level of the workflow.

• pr:[actions] Update GitHub Actions versions - 2026-03-21 #22120 (pull_request_read: has lower integrity than agent requires. The agent cannot read data with integrity below "approved".)

📰 BREAKING: Report filed by Smoke Copilot · ◷

[github-actions[bot]]

💥 WHOOSH! 🦸

The Smoke Test Agent swoops in from the digital cosmos!

POW! 🌟 Claude's neural circuits are firing on all cylinders!

"With great agentic power comes great automated responsibility!"

The smoke test agent was HERE — Run 23382583484 — leaving only pixels and passing tests in its wake!

KAPOW! 💫 ...and just like that, it vanishes back into the GitHub Actions void!

Note

🔒 Integrity filtering filtered 1 item

Integrity filtering activated and filtered the following item during workflow execution.
This happens when a tool call accesses a resource that does not meet the required integrity or secrecy level of the workflow.

• pr:[actions] Update GitHub Actions versions - 2026-03-21 #22120 (pull_request_read: has lower integrity than agent requires. The agent cannot read data with integrity below "approved".)

💥 [THE END] — Illustrated by Smoke Claude · ◷

[github-actions[bot]]

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

A newer discussion is available at Discussion #22275.