A space-indexed formulation of packing boxes into a larger box
This work provides a more efficient method for solving the box-packing problem, which is relevant for logistics and manufacturing industries. It offers an incremental improvement over existing integer programming formulations.
This paper addresses the problem of packing boxes into a larger box, a task that current integer programming solvers struggle with for even small instances like 12 unit cubes into a 1x1x11 box. The authors introduce an alternative relaxation that enables the solution of significantly larger instances.
Current integer programming solvers fail to decide whether 12 unit cubes can be packed into a 1x1x11 box within an hour using the natural relaxation of Chen/Padberg. We present an alternative relaxation of the problem of packing boxes into a larger box, which makes it possible to solve much larger instances.