🧩 Constraint Solving POTD:Problem of the Day: 3D Bin Packing

[github-actions[bot]]

Problem Statement

The 3D Bin Packing Problem is the task of packing a set of rectangular boxes into the minimum number of larger containers (bins) while respecting size constraints and the physical constraint that boxes cannot overlap.

Given:

• n boxes, each with dimensions w_i × h_i × d_i (width, height, depth) and value/weight v_i
• Identical bins of fixed dimensions W × H × D

Find:

• An assignment of boxes to bins
• A 3D placement (coordinates) of each box within its assigned bin
• Minimize the number of bins used

Concrete Instance

Suppose we have 5 boxes and bins of size 10 × 10 × 10:

Box	Width	Height	Depth
A	5	5	4
B	4	6	3
C	3	3	5
D	6	4	4
E	2	2	2

Question: Can all boxes fit into 2 bins?

---

Why It Matters

Logistics & Warehousing: Companies like Amazon, UPS, and FedEx solve 3D packing daily to minimize shipping containers, fuel costs, and carbon footprint. Reducing even one container per 1,000 shipments yields massive savings.

Manufacturing & Storage: Factories optimize use of warehouse space, pallets, and shipping containers. Inefficient packing directly increases operational costs.

Cloud Computing: Data center operators use bin packing variants to allocate virtual machines to physical servers, balancing compute density with thermal and power constraints.

E-commerce: Real-time packing algorithms determine which items can ship together, affecting delivery speed and customer satisfaction.

---

Modeling Approaches

Approach 1: Constraint Programming with Continuous Coordinates

Paradigm: CP with real-valued or discretized coordinates

Decision Variables:

• bin[i] ∈ {1, 2, ..., B}: which bin each box i is assigned to
• x[i], y[i], z[i] ∈ [0, W−w_i], [0, H−h_i], [0, D−d_i]: 3D placement of box i's lower-left corner

Key Constraints:

1. Domain: x[i] + w[i] ≤ W, y[i] + h[i] ≤ H, z[i] + d[i] ≤ D  (fit in bin)
2. Non-overlap: ∀ distinct i,j in same bin:
     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]  OR
     z[i] + d[i] ≤ z[j]  OR  z[j] + d[j] ≤ z[i]
3. Cardinality: bin_used[b] = 1 ⟺ ∃i: bin[i] = b

Objective: Minimize ∑_b bin_used[b]

Trade-offs:

• ✓ Expressive: handles guillotine and non-guillotine layouts
• ✗ Disjunctive constraints (non-overlaps) are hard to propagate efficiently
• ✗ Continuous/mixed domains require discretization or continuous relaxation

---

Approach 2: Mixed Integer Programming (MIP) with Guillotine Cuts

Paradigm: MIP with binary/integer variables

Decision Variables:

• x[b,i] ∈ R: coordinate of box i in bin b (only if assign[b,i] = 1)
• assign[b,i] ∈ {0,1}: whether box i is in bin b
• y_cuts[b,k] ∈ R: guillotine cut positions (enforce axis-aligned rectangular subdivisions)
• use[b] ∈ {0,1}: whether bin b is used

Key Constraints:

1. Assignment: ∑_b assign[b,i] = 1  ∀i
2. Fit in bin: x[b,i] + w[i] ≤ W · assign[b,i]  ∀b,i
3. Non-overlap (via big-M): 
     x[b,i] + w[i] ≤ x[b,j] + W·(1 - (assign[b,i] ∧ assign[b,j]))
   OR similar for other dimensions
4. Bin activation: assign[b,i] ≤ use[b]  ∀b,i

Objective: Minimize ∑_b use[b]

Trade-offs:

• ✓ Leverages mature MILP solvers (CPLEX, Gurobi, open-source)
• ✓ Big-M bounds provide strong relaxations
• ✗ Big-M values can be loose, slowing branch-and-bound
• ✗ Scales poorly for large instances; typically solved heuristically

---

Example Model (MiniZinc Pseudo-code)

int: n;  % number of boxes
int: B;  % max bins
int: W; int: H; int: D;  % bin dimensions

array [1..n] of int: w, h, d;  % box dimensions

% Decision variables
array [1..n] of var 1..B: bin;
array [1..n] of var 0..W: x;
array [1..n] of var 0..H: y;
array [1..n] of var 0..D: z;

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

% Non-overlap: disjunctive constraint
constraint forall (i, j in 1..n where i < j) (
  bin[i] != bin[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] \/
   z[i] + d[i] <= z[j] \/ z[j] + d[j] <= z[i])
);

% Minimize number of bins used
var int: num_bins = max(bin);
solve minimize num_bins;

---

Key Techniques

1. Disjunctive Constraint Propagation

The non-overlap constraints in 3D packing are inherently disjunctive: for any two boxes in the same bin, at least one of six possible separation relations must hold (left, right, front, back, below, above). Modern CP solvers use constraint propagation algorithms such as:

• Interval reasoning: prune placement domain based on partial orderings
• Feasibility-driven labeling: detect infeasible partial orderings early
• Dominance reasoning: eliminate clearly suboptimal placements

2. Layer-Based Heuristics & Decomposition

Practical solvers often decompose 3D packing into layers:

• Bottom-left heuristic: for each box, place it at the lowest available position, then leftmost; repeat for z-layers
• Constraint relaxation: solve a 2D bin packing subproblem per layer, then verify 3D feasibility
• Local search: iteratively shuffle boxes between bins and refine placements

3. Symmetry Breaking & Ordering Constraints

3D packing has massive symmetry (permutations of boxes and bins). Break symmetry by:

• Lex-ordering: enforce x[1] ≤ x[2] ≤ ... ≤ x[n] or similar within each bin
• Bin activation ordering: ensure bin 1 is used before bin 2, etc.
• Dominance constraints: reduce equivalent placements (e.g., only allow placements touching a bin wall)

---

Challenge Corner

Question 1: Suppose all boxes are identical cubes (1 × 1 × 1) and the bin is 10 × 10 × 10. What is the theoretical maximum number of cubes that can be packed? Now, can you formulate a lower bound on the number of bins needed for a mixed set of boxes without actually solving the packing?

Question 2: Extend the problem to include priorities or due dates for shipment: box i must ship in bin b by time t_i. How would you model this as a constraint program? What new propagation techniques might you use?

Question 3: In practice, companies often use heuristic solutions (e.g., genetic algorithms, simulated annealing) rather than exact methods. What properties of 3D packing make metaheuristics attractive? When would you prefer an exact solver over a heuristic?

---

References

1. Pisinger, D. & Sigurd, M. (2005). "Using Genetic Algorithms to Solve Production-Scheduling Problems." Journal of the Operational Research Society, 56(3), 269–281.

   • Comprehensive overview of bin packing and genetic algorithm approaches.

2. Crainic, T. G., Perboli, G., & Mancini, S. (2012). "Models for evaluating and planning city logistics systems." Transportation Research Part E, 48(6), 1172–1199.

   • Real-world applications in urban logistics and 3D packing.

3. Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier.

   • Chapter on global constraints and disjunctive scheduling provides deeper theory.

4. Eley, M. (2010). "Solving container ship cargo planning problems by error correction methods." European Journal of Operational Research, 201(2), 418–426.

   • Domain-specific heuristics and industrial solvers for maritime logistics.

---

Thanks for engaging with today's problem! Share your modeling insights or test cases in the comments below.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 8.78 AIC · ⌖ 7.97 AIC · ⊞ 6.1K · ◷

• expires on Oct 14, 2026, 3:36 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 #66856.