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.

Downloads:

• space-indexed.pdf: A pre-print of our paper A Space-Indexed Formulation of Packing Boxes into a Larger Box.
• pigeon.zip: LP/MPS files for instances of difficult 3D packing problems. The problems are named "Pigeon-n.mps" and "Pigeon-n.lp" where n represents the number of boxes (of size 10x10x10) to pack into a 11x11x(10(n-1)) sized container. The current best commercial solvers (CPLEX and Gurobi) can only optimally solve/close the gap for up to n=10 within one hour. SCIP combined with CPLEX or Gurobi as the LP solver can only pack up to n=8 and n=9 respectively within the hour.
• van-loading.zip, sa_sax.zip: Van loading instances and the sa/sax instances, described in the above paper, in a format resembling Bischoff/Ratcliff test files. A single 'v' is added at the beginning of the file and extra attributes per box type, i.e. the last 3 attributes per box type are payload (mass), knapsack value, and maximum number of boxes of this type allowed in the packing. The format for the sa/sax instances is:
  containerWidth
  containerLength
  containerHeight
  boxWidth boxLength boxHeight
  boxWidth boxLength boxHeight
  boxWidth boxLength boxHeight
  boxWidth boxLength boxHeight
  ...
  
  
• spaceindexed.zip: The source code for the discretised model builder/solver. You'll need Gurobi Solver 3 or higher, or it can probably be made to work with pretty much any version. The source code is not well documented, but it should compile under both Linux (GCC) and Windows (MSVC), modulo path changes. A Microsoft Visual Studio 2010 project setup is included. It is released under the LGPL v3 license.

License

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:

• Sam D. Allen, Edmund K. Burke, and Jakub Marecek, A Space-Indexed Formulation of Packing Boxes into a Larger Box, OR Letters, to appear. Available on-line.

Go back to Jakub's homepage if you want.