🧩 Constraint Solving POTD:Strip Packing — Fitting Rectangles Without Overlap

[github-actions[bot]]

Category: Packing & Cutting · April 11, 2026

---

Problem Statement

Given a strip of fixed width W and unlimited height, and a set of n rectangular items each with width w_i and height h_i, pack all items into the strip without overlap while minimising the total height used.

Items may not be rotated (in the basic version), and every item must lie fully within the strip boundaries.

Small Concrete Instance

Strip width W = 10. Five items:

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

A feasible packing uses height 9; can you find a packing with height ≤ 8?

Decision variables: x_i (horizontal position, left edge), y_i (vertical position, bottom edge).
Objective: minimise H = max_i(y_i + h_i).
Constraint: no two items may overlap.

---

Why It Matters

• PCB and VLSI layout: placing circuit components on a board of fixed width to minimise board length directly reduces material cost.
• Sheet-metal and timber cutting: industries cut rectangular pieces from rolls of fixed width; minimising the roll length consumed reduces waste.
• Newspaper and magazine layout: columns of fixed width must accommodate articles and images with minimal white space.
• Warehouse shelving: placing items of varying heights on shelves of fixed depth.

---

Modeling Approaches

Approach 1 — Constraint Programming with diffn

CP is a natural fit: the non-overlap requirement maps directly onto a global geometric constraint.

Variables:

x_i ∈ [0, W - w_i]          for each item i
y_i ∈ [0, H_ub - h_i]       where H_ub is an upper bound on height
H   ∈ [H_lb, H_ub]           height to minimise
```

**Constraints:**
```
diffn([x_1,...,x_n], [y_1,...,y_n],
      [w_1,...,w_n], [h_1,...,h_n])   // no pairwise overlap

H = max_i(y_i + h_i)
```

**Trade-offs:** `diffn` provides strong propagation via sweep-line and energy reasoning. CP naturally handles discrete decisions and symmetry breaking but may struggle for large `n` without strong bounds on `H`.

---

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

Use binary variables to encode the four relative positions of each pair of items.

**Variables:**
```
x_i, y_i  ∈ R≥0              continuous positions
a_ij ∈ {0,1}                  item i is entirely left of j
b_ij ∈ {0,1}                  item i is entirely right of j
c_ij ∈ {0,1}                  item i is entirely below j
d_ij ∈ {0,1}                  item i is entirely above j
```

**Constraints (for each pair i < j):**
```
a_ij + b_ij + c_ij + d_ij ≥ 1        // at least one separation holds

x_i + w_i ≤ x_j + W(1 - a_ij)       // i left of j
x_j + w_j ≤ x_i + W(1 - b_ij)       // j left of i
y_i + h_i ≤ y_j + H_ub(1 - c_ij)   // i below j
y_j + h_j ≤ y_i + H_ub(1 - d_ij)   // j below i

Trade-offs: LP relaxations yield useful dual bounds, and branch-and-bound is mature. However, the big-M coefficients weaken LP relaxations; O(n2) binary variables scale poorly for large instances.

---

Example Model — MiniZinc (CP approach)

include "globals.mzn";

int: n = 5;
int: W = 10;
array[1..n] of int: w = [4,6,3,5,2];
array[1..n] of int: h = [3,2,5,4,6];

int: H_ub = sum(h);  % worst case: stack all items

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

% Width bounds
constraint forall(i in 1..n)(x[i] + w[i] <= W);

% No overlap via diffn
constraint diffn(x, y, w, h);

% Height definition
constraint H = max(i in 1..n)(y[i] + h[i]);

% Symmetry break: largest item anchored bottom-left
constraint y[1] = 0;

solve minimize H;

output ["Height = \(H)\n"] ++
       [show(x[i]) ++ "," ++ show(y[i]) ++ "\n" | i in 1..n];

---

Key Techniques

1 — Energy-Based Lower Bounds

The area lower bound H_lb = ⌈(Σ w_i · h_i) / W⌉ is fast and tight in practice. Stronger slice bounds sum item heights within horizontal slices; these can be computed once and used to prune H aggressively before search begins.

2 — Sweep-Line Propagation inside diffn

The diffn global constraint uses a sweep-line algorithm (Beldiceanu & Contejean, 1994) that detects infeasibility and prunes domains in O(n log n) per propagation call. It reasons about energy: if the total area of items whose x-ranges overlap a column segment exceeds W × segment_height, the packing is infeasible.

3 — Symmetry Breaking

Two standard symmetries inflate the search space:

• Horizontal reflection: if (x_i, y_i) is optimal, so is (W - x_i - w_i, y_i). Break by fixing x[largest_item] ≤ W/2.
• Identical items: if items i and j have the same dimensions, enforce a lexicographic ordering (x_i, y_i) ≤_lex (x_j, y_j).
• Layer-based symmetry: two items at the same height with no horizontal interaction are interchangeable — handle with a canonical ordering on y.

A first-fit decreasing height (FFDH) heuristic provides a good upper bound and a warm start for both MIP and CP solvers.

---

Challenge Corner

Extension — Allow 90° Rotation

Introduce a binary variable r_i ∈ {0,1} for each item. When r_i = 1, the item is rotated: its effective width becomes h_i and height becomes w_i.

• How does this change the diffn constraint call?
• Does allowing rotation always reduce the optimal height? Can you construct a counterexample?
• Rotation doubles the symmetry space — what new symmetry-breaking constraints would you add?

Bonus — Strip Packing vs. Bin Packing

Can you reduce Strip Packing to a sequence of Bin Packing decisions (one "bin" per horizontal layer of height 1)? What does this cost in model size? When is the layer-based formulation better or worse than the coordinate-based one?

---

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 covering strip packing, bin packing, and cutting stock variants.

2. Beldiceanu, N., & Contejean, E. (1994). Introducing global constraints in CHIP. Mathematical and Computer Modelling, 20(12), 97–123. — Original paper introducing diffn and sweep-line propagation.

3. Clautiaux, F., Jouglet, A., Carlier, J., & Moukrim, A. (2008). A new constraint programming approach for the orthogonal packing problem. Computers & Operations Research. — CP-specific techniques including energetic reasoning and forbidden patterns.

4. MiniZinc Handbook — diffn global constraint. [minizinc.org/doc]((www.minizinc.org/redacted) — Practical reference for using diffn with optional items and the diffn_k generalisation to k dimensions.

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

• expires on Apr 18, 2026, 12:54 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 #26027.