🧩 Constraint Solving POTD:Problem of the Day: Strip Packing Problem

[github-actions[bot]]

Problem Statement

What Is Strip Packing?

Strip packing is the problem of arranging a collection of rectangular items into a strip of fixed width and minimal height. Imagine a roll of material with a fixed width—your goal is to pack all items onto this roll using the least amount of material length.

Concrete Instance:
Given 8 rectangular items with dimensions (width × height):

• Item 1: 3×5, Item 2: 4×3, Item 3: 2×7, Item 4: 5×2
• Item 5: 3×4, Item 6: 4×6, Item 7: 2×2, Item 8: 3×3

Pack them into a strip of width 10, minimizing the total height (depth) of the strip.

Input/Output:

• Input: Set of rectangles {(w_i, h_i)}, strip width W
• Output: Positions {(x_i, y_i)} for each item such that:
  • No item overlaps
  • All items fit within strip width W
  • Total height is minimized

---

Why It Matters

Cutting Stock & Manufacturing:
Paper mills, textile manufacturers, and sheet metal suppliers use strip packing daily. Minimizing waste on fixed-width rolls directly reduces material costs.

VLSI Design:
Circuit layout engineers pack logic blocks onto silicon dies with fixed width to minimize die area and manufacturing cost.

Web Layout & UI Rendering:
Browsers and design tools use variants of strip packing to arrange components in fixed-width containers.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Paradigm: Declarative constraint satisfaction with geometric constraints.

Decision Variables:

• x[i] ∈ [0..W-w_i] — horizontal position of item i
• y[i] ∈ [0..H_max] — vertical position of item i
• H ∈ [h_max..H_max] — total height (minimize this)

Key Constraints:

1. Non-overlap: For all pairs (i,j):
   x[i] + w[i] ≤ x[j] ∨ x[j] + w[j] ≤ x[i] ∨
   y[i] + h[i] ≤ y[j] ∨ y[j] + h[j] ≤ y[i]

2. Bounds: y[i] + h[i] ≤ H  for all i

3. Symmetry-breaking:
   x[i] + w[i] ≤ W  for all i

Global Constraint: cumulative/4 or nonoverlap_2d can encode non-overlap efficiently.

Trade-offs:

• ✅ Expressive, handles diverse constraints naturally
• ✅ Strong propagation with global constraints
• ❌ Disjunctive constraints create search branching

---

Approach 2: Mixed-Integer Linear Programming (MIP)

Paradigm: Optimize over linear constraints with binary indicators.

Decision Variables:

• x[i], y[i] as before (continuous relaxation: x[i] ∈ [0..W])
• z[i,j] ∈ {0,1} for each pair (i,j): binary indicator of relative position

Key Constraints:

1. Non-overlap linearization (big-M encoding):
   x[i] + w[i] ≤ x[j] + M(1 - z[i,j,0])
   x[j] + w[j] ≤ x[i] + M·z[i,j,0]
   y[i] + h[i] ≤ y[j] + M(1 - z[i,j,1])
   y[j] + h[j] ≤ y[i] + M·z[i,j,1]
   z[i,j,0] + z[i,j,1] ≥ 1  (at least one must hold)

2. Objective: minimize H
   where y[i] + h[i] ≤ H  for all i

Trade-offs:

• ✅ Continuous relaxation gives bounds; branching on binary variables
• ✅ Scalable to large instances with modern MIP solvers
• ❌ Big-M formulations are weak without careful tuning
• ❌ More variables and constraints than CP model

---

Example CP Model (MiniZinc)

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

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

% Non-overlap
constraint forall(i,j in 1..n where i < j) (
  x[i] + w[i] <= x[j] \/ 
  x[j] + w[j] <= x[i] \/ 
  y[i] + h[i] <= y[j] \/ 
  y[j] + h[j] <= y[i]
);

% Bounds
constraint forall(i in 1..n) (
  x[i] + w[i] <= W /\ y[i] + h[i] <= H
);

solve minimize H;

---

Key Techniques

1. Global Constraint Propagation

The nonoverlap_2d or cumulative global constraint exploits the geometry of the problem:

• Sweep-line algorithms compute contours of packed items, detecting infeasibility early
• Prunes variable domains more aggressively than pairwise constraints alone
• Cost: ~O(n2 log n) per consistency check, but pays off in reduced search tree

2. Heuristic Ordering & Greedy Seeding

Most-constrained variable heuristics (e.g., largest-first) pack bigger items early:

• Reduces the search space by committing to dominant structures
• Bottom-left heuristic: place each item at lowest possible position, then leftmost
  – Often finds good feasible solutions quickly (seed for branch-and-bound)

3. Symmetry-Breaking Inequalities

Strip packing has reflection and rotation symmetries:

• Add constraints like x[1] < x[2] (break lexicographic symmetry)
• Enforce item ordering when sizes are tied: reduces redundant branches by ~n!/2^n
• Lex-leader constraints (e.g., canonical orderings) cut off symmetric solutions

---

Challenge Corner

Open Questions for You:

1. Can you reduce problem size?
   Can you model this with a single continuous variable per item (e.g., just y[i] if items are sorted by width)?
   What assumptions would you need to add?

2. Rotations & Guillotine Cuts:
   How would you extend the model to allow 90° rotations of rectangles?
   What about enforcing guillotine cuts (nested rectangular partitions) to speed up packing?

3. Online vs. Offline:
   If items arrive one at a time (online variant), what greedy strategies are provably near-optimal?
   How does offline knowledge improve the solution?

---

References

1. Lodi, A., Martello, S., & Monaci, M. (2002). "Two-dimensional packing problems: a survey." European Journal of Operational Research, 141(2), 241–252.
   – Definitive survey covering variants, exact methods, and heuristics.

2. Korf, R. E. (2003). "Optimal rectangle packing: Initial results." Proc. ICAPS-03, 287–295.
   – Exact algorithms for small-to-medium instances; excellent introduction to bounding techniques.

3. Hopper, E., & Turton, B. C. (2001). "A review of the application of meta-heuristic algorithms to 2D strip packing problems." Artificial Intelligence Review, 16(4), 257–300.
   – Survey of local search and genetic algorithms; practical solver techniques.

4. MiniZinc Handbook ((www.minizinc.org/redacted)
   – Global constraint documentation, including nonoverlap_2d and rectangle packing examples.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 7.99 AIC · ⌖ 7.26 AIC · ⊞ 6.2K · ◷

• expires on Sep 15, 2026, 3:34 AM UTC-08:00

[github-actions[bot]]

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

A newer discussion is available at Discussion #59704.