Exploiting Packing Components in General-Purpose Integer Programming Solvers

Jakub MarecekarXiv 2014 · DOI · OpenReview

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.

Constraint matrix visualization showing the structured blocks of rows in a packing problem.

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.

Sparsity pattern of a larger constraint matrix, highlighting the scalability of the structural detection.
  • 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

Abstract

The problem of packing boxes into a large box is often a part of a larger problem. For example in furniture supply chain applications, one needs to decide what trucks to use to transport furniture between production sites and distribution centers and stores, such that the furniture fits inside. Such problems are often formulated and sometimes solved using general-purpose integer programming solvers. This chapter studies the problem of identifying a compact formulation of the multi-dimensional packing component in a general instance of integer linear programming, reformulating it using the discretisation of Allen--Burke--Marecek, and and solving the extended reformulation. Results on instances of up to 10000000 boxes are reported.
BibTeX
@misc{marecek2014exploiting,
  author = {Jakub Marecek},
  title = {{Exploiting Packing Components in General-Purpose Integer Programming Solvers}},
  year = {2014},
  eprint = {1412.2526},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1412.2526},
}
Figure