Logistics

A Minimalist 3D Bin Packing Algorithm & Universal CSP Solver

Charles Dana & Claude — April 2026

Original manuscript: ORIJ-D-23-00102, Operational Research, March 2023

Repo: logistics.aws.monce.ai

Abstract

This article introduces Logistics: a minimalist 3D bin packing algorithm that clusters items within a container while minimizing empty space. The algorithm uses package superposition to simulate the presence of a single box at multiple places, reducing the number of operations needed to fill the container. The algorithm can be viewed as a Markov chain on the space of multiple partial solutions, enabling it to explore the solution space efficiently.

We show that the same framework — superposition + conflict-oriented random walk — generalizes to any constraint satisfaction problem: Graph Coloring, SAT, Sudoku, N-Queens, and in principle any NP-complete problem reducible to CSP.

1. The Framework

The core insight is that many combinatorial optimization problems share the same structure:

1. Variables — things you're assigning (items, vertices, boolean vars, cells, rows)
2. Domains (Φ sets) — candidate values per variable (positions, colors, {T,F}, digits, columns)
3. Conflict predicate — any polynomial-time checkable pairwise constraint (overlap, adjacency, clause violation, duplicate-in-group, diagonal attack)

The solver operates on X_t = Π Φ(i): the Cartesian product of all domains. Each state is a complete assignment. The Markov chain walks this space by:

1. Detecting a conflict (a, b) via the conflict-oriented heuristic
2. Re-assigning one of the conflicting variables to a new value from its domain
3. Accepting improvements, tolerating lateral moves, and using SA for worse moves

2. Definitions (from the 2023 paper)

Definition 1: Orthogonal 3DBPP

Given {(a_i, b_i, c_i, i) : i ≤ n} rectangular shapes and a container (A, B, C), find an anchor function A : (a_i, b_i, c_i, i) ↦ (x_i, y_i, z_i) ∈ [0,A] × [0,B] × [0,C] such that no two items overlap.

Definition 2: Package Superposition (Φ)

Φ : i ↦ {(x_i,t, y_i,t, z_i,t) : t ≤ m_i} maps each item to a set of candidate placements. The algorithm explores the Cartesian product X₀ = Π Φ(i), narrowing to a consistent assignment.

In the implementation, Φ is generated using an item-dimension-aligned grid: candidate positions at multiples of all item dimensions present in the problem. This produces a compact but complete set of structurally meaningful positions.

Definition 3: Fast Collision Detection

Two placements collide iff they overlap on all three axes (separating axis theorem):

Computed in O(1) per pair, O(n²) for all pairs.

Definition 4: Clustering

Identical items are grouped and placed as block arrangements (nx × ny × nz grids). This reduces the effective problem size for homogeneous item sets.

Definition 5: Bounded Random Walk

The state X_t evolves via: at each step, pick a conflicting pair, re-assign one variable. The process is a random walk on [0, n ln(M)] with step size ln(1 ± 1/M), where M = max |Φ(i)|.

Proposition 1 (Convergence)

Under the assumption that fast collision detection contradicts X_t in O(n^a) time, the process converges with probability approaching 1 when N ≥ M² n ln M steps. The probabilistic upper bound: O(n^a+1 M² ln M).

3. The Generalization

The 3DBPP-specific definitions map directly to a general CSP:

The solver code is identical. Only the variable/domain/conflict definitions change:

4. Implementation Optimizations

4.1 Greedy Initialization

Instead of random X₀, we place variables in decreasing order of constraint difficulty (largest item / smallest domain first). For each, we sample up to 20 candidates and pick the one with fewest conflicts. This often solves easy instances in 0 Markov chain iterations.

4.2 Incremental Conflict Tracking

Instead of O(n²) full conflict scan per iteration, we maintain per-variable conflict counts and update only the affected neighborhood when a variable changes: O(degree) per iteration.

4.3 Arc Consistency (AC-3)

For Sudoku and similar tightly-constrained CSPs, we run AC-3 preprocessing to prune domains before the Markov chain. This alone solves easy Sudoku instances (the domain collapses to singleton sets via propagation).

4.4 Domain-Specific Solvers

N-Queens uses a specialized min-conflicts solver with O(1) conflict counting via column/diagonal counters. This enables solving 1000-Queens in ~230ms.

5. Experimental Results

5.1 3D Bin Packing

Perfect tilings solved: 8 cubes in 4³, 27 cubes in 9³, 64 cubes in 12³. Solution validity verified: all items in bounds, zero collisions, valid orientations. 50/50 random instances solved and verified.

5.2 Graph Coloring

5.3 SAT

5.4 Sudoku

Honest limitation: the Markov chain excels at resolving local conflicts but cannot perform the global constraint propagation that hard Sudoku puzzles require. This is exactly the gap between local search and DPLL/CDCL.

5.5 N-Queens

6. Complexity

Bin Packing: Greedy init O(n · |Φ| · n), Markov chain O(iterations · n) per step. With item-aligned grid, |Φ| is polynomial in container size.

CSP (general): Greedy init O(n · |D| · deg), Markov chain O(iterations · deg) per step with incremental tracking. AC-3 preprocessing: O(e · d²) where e = edges, d = max domain.

N-Queens: O(n) per iteration with column/diagonal counters. Empirically near-linear total iterations in n.

7. Connection to AUMA

The Logistics framework shares DNA with AUMA (Dana, 2023):

• AUMA: f: {0,1}ⁿ → R is a weighted MAXSAT instance. Search via local walk on weighted clauses.
• Logistics: CSP assignment is a point in Π Φ(i). Search via Markov chain on the product space.

Both encode the problem as "pick one value per variable from a finite domain" and walk the space. The Φ function in Logistics plays the same role as the clause set W in AUMA. The conflict predicate is the analogue of clause evaluation.

The lineage: AUMA (2023) → Dana Theorem (2024) → Snake (SAT classifier) → Logistics (CSP solver). Each step narrows the gap between "everything is MAXSAT" and "how much of combinatorial optimization is tractable with the right framework."

8. What Logistics Does NOT Claim

• It does not claim P = NP. The Markov chain has exponential worst-case.
• Hard Sudoku (17 clues) and very tight bin packing (>75% fill) can fail.
• The SAT encoding uses pairwise approximation, not full clause evaluation.
• N-Queens uses a specialized solver, not the generic CSP loop.

The contribution is the framework: one algorithm structure that works across multiple NP-complete problems by changing only the domain and conflict definitions. The experiments show where it excels (bin packing, graph coloring, N-Queens) and where it struggles (hard Sudoku, very tight 100% tilings).

API Reference

References

1. Dana, C. (2023). A O(2^n/2) Universal Maximization Algorithm. MSc thesis, Ecole Polytechnique.
2. Levin, D.A., Peres, Y., Wilmer, E.L. (2009). Markov Chains and Mixing Times. AMS.
3. Lovász, L. (1993). Random Walks on Graphs: A Survey. Paul Erdos is Eighty, Vol. 2.
4. Hopper, E. & Turton, B. (2001). A survey of results and recent work on the 3D bin packing problem. JORS, 52(1).
5. Vázquez-Rodríguez, J.A. et al. (2013). A hybrid heuristic for the 3D bin packing problem. C&OR, 40(12).
6. Martello, S. & Toth, P. (1990). Knapsack Problems. Wiley.

Back to Logistics