🧩 Constraint Solving POTD:Problem of the Day: Rectangle Packing (2D Bin Packing)

[github-actions[bot]]

Problem Statement

Rectangle Packing (or 2D bin packing) asks: given a set of rectangular items, each with width w_i and height h_i, and a container (or "bin") of fixed dimensions W × H, can we fit all items into the container without overlaps? If there is space left over, can we minimize the number of containers needed?

Concrete Instance

Suppose you have a roll of fabric that is 1000 cm × 800 cm, and you need to cut out these rectangular garment panels:

• 5 panels of 400 × 300 cm
• 3 panels of 350 × 250 cm
• 4 panels of 200 × 400 cm
• 6 panels of 250 × 150 cm

Can all 18 panels fit in a single roll? If not, how many rolls are needed?

Input/Output Specification

Input:

• A set of items, each with (width_i, height_i)
• A container dimension (W, H)
• Decision variables: placement coordinates (x_i, y_i) for each item's bottom-left corner
• Optional: rotation allowed or not (we may rotate items 90°)

Output:

• Feasibility: a valid placement of all items with no overlaps, or "infeasible"
• Minimization: use the fewest bins possible to pack all items

---

Why It Matters

Textile and apparel manufacturing: Cutting panels from large bolts of fabric or leather minimizes waste and cost—waste can account for 10–20% of material in real operations.

Semiconductor manufacturing: Placing circuit designs on wafer dies requires optimal spatial layout to maximize yield and minimize defects from edge effects.

Furniture and sheet-metal fabrication: Nesting parts on standard blanks or sheets reduces scrap and production time, directly impacting profit margins.

Warehousing and logistics: Packing boxes onto pallets or truck beds in 2D or 3D arrangements improves space utilization and reduces shipping costs.

---

Modeling Approaches

Approach 1: Constraint Programming (CP) with Non-Overlap Constraints

Paradigm: Declarative constraint programming with a global constraint.

Decision Variables:

• x_i, y_i ∈ [0, W - w_i] × [0, H - h_i] for each item i

Key Constraints:

for all pairs (i, j) with i < j:
  x_i + w_i ≤ x_j  OR  x_j + w_j ≤ x_i  OR
  y_i + h_i ≤ y_j  OR  y_j + h_j ≤ y_i

This disjunctive constraint ensures items do not overlap (at least one inequality in each "OR" must hold).

Trade-offs:

• Strength: Compact, expressive, natural representation; many solvers (Gecode, Chuffed) have specialized global constraints for rectangle packing.
• Weakness: Disjunctive constraints can be expensive to propagate; branch-and-bound search may require careful variable/value ordering.
• Scalability: Works well for ~50 items; beyond 100, scalability degrades without advanced techniques.

Approach 2: Mixed-Integer Programming (MIP)

Paradigm: Linear algebraic formulation with continuous and binary variables.

Decision Variables:

• x_i, y_i (continuous): placement coordinates
• z_ij ∈ {0, 1} (binary): indicator that item i is to the left of item j

Key Constraints:

For each pair (i, j):
  x_i + w_i ≤ x_j + M·(1 - z_ij)      [if z_ij = 1, i is left of j]
  x_j + w_j ≤ x_i + M·z_ij             [if z_ij = 0, j is left of i]
  y_i + h_i ≤ y_j + M·(1 - z_ij')     [if z_ij' = 1, i is below j]
  ...and similar y-constraints

where M is a large constant and z_ij ⊕ z_ij' ensures exactly one spatial relation holds.

Trade-offs:

• Strength: LP relaxations provide good lower bounds; standard MIP solvers (CPLEX, Gurobi) are highly optimized.
• Weakness: Many binary variables (O(n2)); the LP relaxation can be loose, requiring strong branching.
• Scalability: Good for problems with 100–200 items when high-quality bounds suffice; beyond that, specialized heuristics are preferable.

Approach 3: Hybrid CP + Local Search

Paradigm: Start with a CP or greedy solution; refine iteratively via local moves.

Idea:

1. Use a fast greedy algorithm (e.g., Next Fit Decreasing or First Fit Decreasing) to get an initial packing.
2. Apply local search or Large Neighborhood Search (LNS) to improve:
   • Slide: slide an item slightly to open gaps for other items.
   • Rotate: flip an item 90° and re-pack neighbors.
   • Swap: exchange positions of two items.
3. Use constraint propagation to verify feasibility after each move.

Trade-offs:

• Strength: Scales to thousands of items; practical for real-world instances.
• Weakness: No guarantee of optimality; solution quality depends on neighborhood design and local search strategy.
• Scalability: Excellent; most industrial packing systems use variants of this approach.

Example Model (MiniZinc Subset)

% 2D Rectangle Packing (simplified)
int: n;                          % number of items
int: W; int: H;                  % bin dimensions
array[1..n] of int: w, h;        % item widths and heights

var 0..W-1: x[1..n];             % x-coordinate of each item
var 0..H-1: y[1..n];             % y-coordinate of each item

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

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]
);

solve satisfy;
output [show(x), "
", show(y)];

This model uses disjunctive constraints (the \/ operator) to enforce non-overlaps.

---

Key Techniques

1. Disjunctive Propagation & Arc Consistency

When a pair of items has only one feasible spatial relation (e.g., item A must be strictly left of item B), propagate this across the entire problem. Tools like cumulative global constraints in CP solvers use specialized algorithms to prune infeasible configurations early.

2. Greedy Heuristics for Initialization

Next Fit Decreasing (NFD): sort items by area in decreasing order; place each item as early as possible using a simple rule (e.g., bottom-left corner). Fast (O(n log n)) and often yields solutions within 10–20% of optimal.

3. Symmetry Breaking

The same packing can be represented many ways (translate items, reorder identical items). Breaking these symmetries reduces search space:

• Lexicographic ordering: enforce x_1 ≤ x_2 ≤ ... ≤ x_n
• Tie-breaking: if two items are identical, impose a fixed order.

---

Challenge Corner

1. Rotation freedom: How would you model the rectangle packing problem if items can be rotated 90°? What additional variables and constraints are needed?

2. Bin minimization: If the bin dimension is unlimited in one direction (like a continuous roll), can you reformulate this as a 1D packing problem with a single height constraint?

3. Symmetry and dominance: How many distinct packings are equivalent under rotation, translation, and permutation of items? Can you design symmetry-breaking constraints that reduce the search tree without losing the optimal solution?

---

References

1. Pisinger, D. & Sigurd, M. (2007). "Using genetic algorithms to solve the rectangular bin packing problem." Journal of Heuristics, 13(3), 263–279.

   • Comprehensive survey on genetic algorithms and metaheuristics for 2D packing.

2. Martello, S. & Vigo, D. (1998). "Exact solution of the two-dimensional finite bin packing problem." Management Science, 44(3), 388–399.

   • Foundational work on branch-and-bound methods for 2D bin packing.

3. Clautiaux, F., Carlier, J., & Moukrim, A. (2007). "A new exact algorithm for the two-dimensional orthogonal packing problem." European Journal of Operational Research, 183(3), 1196–1211.

   • Modern exact approaches using constraint propagation and problem-specific cuts.

4. Wäscher, G., Haubner, H., & Schumann, H. (2007). "An improved typology of cutting and packing problems." European Journal of Operational Research, 183(3), 1109–1130.

   • Standard taxonomy and classification of all packing variants.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 7.46 AIC · ⌖ 7.56 AIC · ⊞ 6K · ◷

• expires on Oct 6, 2026, 3:36 AM UTC-08:00