Solvers for 3D Packing Problems

a project of Sam Allen <samallen at users dot sourceforge dot net> (www)
and Jakub Marecek <jakub at marecek dot cz> (www)
supervised by Prof. Edmund K. Burke <ekb at cs dot nott dot ac dot uk> (www).

An Overview

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.



All the files above are licenced under the Lesser GNU Public License (LGPL) version 3. It would be greatly appreciated, however, if users would cite the following:

Go back to Jakub's homepage if you want.