🧩 Constraint Solving POTD:Strip Packing Problem

[github-actions[bot]]

Category: Packing & Cutting | Date: 2026-03-19

---

Problem Statement

Given a set of n rectangles, each with a fixed width w_i and height h_i, pack them without overlap into a strip of fixed width W, minimizing the total height H of the strip used. Rectangles must be axis-aligned (no rotation in the basic version).

Small Concrete Instance

Strip width W = 10. Five rectangles:

Item	Width	Height
1	4	3
2	3	5
3	6	2
4	2	4
5	5	3

A valid (non-optimal) packing places items 1, 2, 4 in the first row (total height 5), items 3 and 5 in the second row (total height 2), yielding H = 7. The area lower bound is (4·3 + 3·5 + 6·2 + 2·4 + 5·3) / 10 = 56/10 = 5.6, so H ≥ 6. An optimal packing achieves H = 6.

Output: (x_i, y_i) coordinates (bottom-left corner) for each rectangle such that all rectangles fit within [0,W] × [0,H] and no two rectangles overlap.

---

Why It Matters

• VLSI & PCB layout: Placing circuit components on a chip or board — strip width is the die boundary; minimizing height reduces material cost directly.
• Newspaper & magazine layout: Fitting articles and images onto a fixed-width page column, minimizing page count or scroll depth.
• Cutting stock & material nesting: Minimizing wasted material when cutting pieces from rolls (fabric, sheet metal, paper) of fixed width.
• Container & shelf loading: Stacking pallets or products in fixed-width shelves or transport containers to minimize height/depth used.

---

Modeling Approaches

Approach 1: Constraint Programming with diffn

The key insight is that non-overlap is a 2D placement constraint. CP solvers expose it directly.

Decision variables:

• x_i ∈ [0, W - w_i] — horizontal position of item i
• y_i ∈ [0, H_max - h_i] — vertical position of item i
• H — objective: total strip height

Constraints:

diffn([x_i], [y_i], [w_i], [h_i])   // global no-overlap (2D)
∀i: y_i + h_i ≤ H                   // items fit within strip height
∀i: x_i + w_i ≤ W                   // items fit within strip width
minimize H
```

The `diffn` (or `nooverlap2d`) global constraint encodes: for every pair `(i,j)`, at least one of `x_i + w_i ≤ x_j`, `x_j + w_j ≤ x_i`, `y_i + h_i ≤ y_j`, `y_j + h_j ≤ y_i` must hold.

**Trade-offs:** Highly expressive; strong propagation (energetic reasoning, not-first/not-last) in mature solvers. Search space can be large for precise coordinate variables; good variable/value ordering is critical.

---

#### Approach 2: Mixed-Integer Programming (MIP)

Encode non-overlap using **big-M disjunctions** over four cases.

**Decision variables:**
- `x_i, y_i` — continuous coordinates (or integer if sizes are integral)
- `δ_ij^d ∈ {0,1}` for `d ∈ {L,R,B,T}` — binary indicator: item `i` is to the left/right/below/above item `j`
- `H` — objective

**Constraints:** For each pair `(i,j)`:
```
x_i + w_i ≤ x_j + M(1 - δ_ij^L)
x_j + w_j ≤ x_i + M(1 - δ_ij^R)
y_i + h_i ≤ y_j + M(1 - δ_ij^B)
y_j + h_j ≤ y_i + M(1 - δ_ij^T)
δ_ij^L + δ_ij^R + δ_ij^B + δ_ij^T ≥ 1     // at least one must hold

Trade-offs: Strong LP relaxations available; can incorporate continuous objectives naturally. Big-M constants weaken LP bounds; number of binary variables grows as O(n²), so scales poorly beyond ~50–100 items without decomposition.

---

Approach 3: Contiguous-Level (Shelf) Decomposition

Rather than exact coordinates, assign each item to a shelf (horizontal strip). A shelf's height equals the tallest item on it.

1. Decide how many shelves k and which items go on each shelf.
2. Verify each shelf's total width ≤ W.
3. H = Σ_shelf max_height(shelf).

Trade-offs: Dramatically reduces the search space; shelf-based packings are sometimes suboptimal (items can't straddle shelf boundaries), so it's a heuristic / restricted model. Works well in practice for real-world cutting problems with natural rows.

---

Example Model (MiniZinc)

include "diffn.mzn";

int: n = 5;
int: W = 10;
array[1..n] of int: w = [4, 3, 6, 2, 5];
array[1..n] of int: h = [3, 5, 2, 4, 3];
int: H_max = sum(h);   % loose upper bound

array[1..n] of var 0..W:     x;
array[1..n] of var 0..H_max: y;
var 1..H_max: H;

constraint diffn(x, y, w, h);
constraint forall(i in 1..n)(x[i] + w[i] <= W);
constraint forall(i in 1..n)(y[i] + h[i] <= H);

% Symmetry breaking: sort by height descending, fix widest item's x
constraint x[1] <= (W - w[1]) div 2;

solve minimize H;

---

Key Techniques

1. Energetic Reasoning (Cumulative Propagation)

Project all rectangles onto the horizontal axis to get a 1D scheduling view. For any interval [a, b], the total area of items whose projections are fully contained in [a, b] cannot exceed (b-a) × H. Violating this tightens H bounds immediately. This is the 2D extension of the cumulative constraint's energetic reasoning.

2. Symmetry Breaking

Strip packing has massive symmetry:

• Horizontal reflection: If (x_i, y_i) is a solution, so is (W - w_i - x_i, y_i). Break by requiring the item with the greatest width to have x ≤ (W - w) / 2.
• Equivalent packings: Two items with identical (w, h) are interchangeable — lexicographic ordering on their coordinates prunes symmetric branches.
• Canonical shelf positions: Optimal packings always have at least one item whose y_i equals 0 or equals the top of another item. Restrict y_i to the finite set of "interesting" positions (sums of subsets of heights) to reduce domain sizes without losing optimality.

3. Lower-Bound Relaxations

Two classic lower bounds to guide search and establish optimality:

• Area bound: H ≥ ⌈Σ(w_i · h_i) / W⌉
• Dual bin-packing bound: Compute via dual-feasible functions — items wide enough to require their own column give a stronger bound. This can be computed in polynomial time and often beats the area bound significantly.

---

Challenge Corner

Extension — Rotations allowed: Suppose each rectangle may be rotated 90° (swapping w_i and h_i). How does this change the model? Add a binary variable r_i ∈ {0,1} and express w_i(r_i) = r_i · h_i + (1-r_i) · w_i — but note this introduces a product of a binary and the coordinate variables. How would you linearize this cleanly in MIP? Can the diffn constraint in CP handle it directly?

Deeper question: The strip packing optimal solution height is NP-hard to compute (it generalizes bin packing). Yet for many practical instances, the area lower bound is tight. Can you characterize the class of instances where the area bound is always tight?

---

References

1. Lodi, A., Martello, S., & Monaci, M. (2002). Two-dimensional packing problems: A survey. European Journal of Operational Research, 141(2), 241–252. — Comprehensive survey of models and algorithms.

2. Korf, R. E. (2003). An improved algorithm for optimal bin packing. IJCAI. — Introduces contiguous-shelf methods with tight lower bounds.

3. Clautiaux, F., Carlier, J., & Moukrim, A. (2007). A new exact method for the two-dimensional orthogonal packing problem. European Journal of OR, 183(3), 1196–1211. — Energetic reasoning and dual-feasible function bounds.

4. MiniZinc Documentation — diffn constraint. [minizinc.org]((www.minizinc.org/redacted) — Practical reference for 2D packing in CP models.

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

• expires on Mar 26, 2026, 2:16 PM UTC

[github-actions[bot]]

🤖 Beep boop! The smoke test agent has materialized in your discussion!

I've been dispatched from the misty realm of automated testing to verify all systems are operational. The strip packing problem is fascinating — minimizing H while the smoke test minimizes flakiness!

The agent was here ✅ (workflow run §23300957794)

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:feat: mount custom GitHub Actions as safe output tools via safe-outputs.actions #21752 (pull_request_read: Resource 'pr:feat: mount custom GitHub Actions as safe output tools via safe-outputs.actions #21752' has lower integrity than agent requires. Agent would need to drop integrity tags [unapproved:all approved:all] to trust this resource.)

📰 BREAKING: Report filed by Smoke Copilot · ◷

[github-actions[bot]]

💥 WHOOSH!!

ZAP! The Smoke Test Agent has arrived! 🦸

KAPOW! Run §23300957786 completed with ALL SYSTEMS NOMINAL!

WHAM! Claude engine: ONLINE ⚡
BOOM! Tools tested: 17/17 🎯

"With great agentic power comes great agentic responsibility!" — Claude, probably

💫 [THE END] — The Smoke Test Agent flies off into the GitHub Actions sunset... until next time! 🌅

Note

🔒 Integrity filtering filtered 2 items

Integrity filtering activated and filtered the following items 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:feat: mount custom GitHub Actions as safe output tools via safe-outputs.actions #21752 (pull_request_read: Resource 'pr:feat: mount custom GitHub Actions as safe output tools via safe-outputs.actions #21752' has lower integrity than agent requires. Agent would need to drop integrity tags [unapproved:all approved:all] to trust this resource.)
• pr:feat: mount custom GitHub Actions as safe output tools via safe-outputs.actions #21752 (pull_request_read: Resource 'pr:feat: mount custom GitHub Actions as safe output tools via safe-outputs.actions #21752' has lower integrity than agent requires. Agent would need to drop integrity tags [approved:all unapproved:all] to trust this resource.)

💥 [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 #21977.