The problem of packing many small boxes into a single larger box underlies a number of cutting, packing, scheduling, and transportation applications. There are a number of heuristic solvers, but the progress in exact solvers, in general, and integer programming solvers, in particular, has been limited. Padberg (Math. Methods Oper. Res., 52(1):1 21, 2000) estimated his extension of the integer linear programming formulation of Chen et al. could cope with "about twenty boxes". Our computational experiments confirm that the seemingly trivial decision whether twelve unit-cubes can be packed into a box with the unit-base and height eleven ("3D Pigeon Hole"), cannot be made within an hour by modern integer programming solvers using this formulation. We present a new, "space-indexed", linear programming relaxation, which often provides lower bounds within 1 percent of optimality, and makes it possible to solve instances of 3D Pigeon Hole problem with ten million boxes within an hour. Results of extensive computational tests of both formulations are reported.
For further details, please see: