Abstract: The problem of packing boxes into a large box is often a part of a larger problem, such as furniture supply chain logistics. These problems are frequently formulated using general-purpose integer programming solvers. This paper explores identifying compact formulations of multi-dimensional packing components within general integer linear programming instances, reformulating them using the discretization of Allen–Burke–Mareček, and solving the resulting extended reformulation. Results demonstrate successful scaling to instances involving up to 10,000,000 boxes.
Introduction
Packing boxes into containers, known as the Container Loading Problem (CLP), is a cornerstone of logistics optimization. Despite its apparent simplicity, it is notoriously difficult for standard solvers. Most real-world applications embed these packing constraints within larger Integer Linear Programming (ILP) models.
The primary challenge is that standard "compact" formulations—which rely on relative positioning (e.g., "box A is to the left of box B")—create a weak linear programming relaxation. This leads to a massive "integrality gap," causing state-of-the-art solvers like CPLEX or Gurobi to fail on even trivial instances, such as packing 12 unit cubes, within an hour.
Methods: Detect and Reformulate
The paper proposes a "detect and reformulate" strategy to overcome these limitations:
Component Extraction
The author provides a formal algorithm (Algorithm 2) to scan a general ILP constraint matrix and identify blocks of rows that represent inefficient packing formulations. This allows the solver to automatically isolate the packing sub-problem in polynomial time without manual intervention.
Space-Indexed Reformulation
Once detected, the component is translated into the Allen–Burke–Mareček formulation. Instead of relative positions, this model uses a grid of binary variables representing whether a specific box type starts at a specific coordinate $(x, y, z)$. This approach provides a much stronger linear relaxation.
Adaptive Discretization
To manage the variable count in large containers, the paper uses heuristics to discretize space. This includes Greatest Common Divisor (GCD) reductions and a Dynamic Programming (DP) approach (Algorithm 3) to identify only "valid" coordinates. While finding the optimal discretization is $\Delta^p_2$-Hard, these heuristics maintain computational tractability.
Key Results
The performance gains from this reformulation are significant, particularly in terms of scalability and relaxation strength.
- Scaling: While standard formulations timed out on 12 boxes, the reformulated model solved a 10-million-box "Pigeon Hole" instance in 664 seconds.
- Integrality Gap: The gap between the theoretical bound and the optimal solution dropped from roughly 10.5% to 0.37%, allowing the solver to prune the search tree almost immediately.
- Efficiency: For the 10-million-box case, the resulting ILP remained tractable despite having over 10 million rows and 30 million non-zeros.
Conclusion
The research highlights that "compactness" in optimization—fewer variables and rows—does not always equate to speed. By exploiting the mathematical strength of space-indexed formulations and automating their detection, general-purpose solvers can be made "packing-aware," drastically improving their performance on complex logistics problems. Future work may apply similar structure-exploiting techniques to other common optimization components, such as graph coloring.
Summary updated