[benzedrine.ch logo]
Contents
Home
Daniel Hartmeier
Packet Filter
pfstat
Mailing list
Annoying spammers
Prioritizing ACKs
Transparent squid
Proxy ICB/IRC
milter-regex
milter-spamd
milter-checkrcpt
login_yubikey
Dorabella
Tron
Planet Wars
Hexiom solver
3D-ODRPP
Polygon partition
Mikero's grid puzzle
Dark Star
Misc
Statistics


A novel packing heuristic based on rigid body simulation

The Vistaprint Tech Challenge 2014 (archived details) asked:

Given a collection of Vistaprint products, what is the smallest shipping box that can contain them? And how should they be packed into that box?

This is a packing problem. According to the typology it is a three-dimensional rectangular open dimension problem (ODP) with three variable dimensions.
Notably, it allows arbitrary, non-orthogonal rotations, and the target is low surface area.

Such problems are NP-complete, and N=100 is a non-trivial size.
Hence, guaranteed optimal solutions are out of reach, instead a good heuristic is sought.
Specifically, it should be fast enough to be run "tens of thousands of times every day", i.e. running time should be less than one second.

In a novel approach, a heuristic algorithm based on solid body dynamics was written in ~350 lines of C++ using the Open Dynamics Engine (ODE) library.
Interestingly, the implementation is embarrasingly parallel, and the quality of the result increases with parallel runs (Monte Carlo method).
Submitted October 13th 2014, results announced (archive) December 3rd 2014. Congratulations to Lars Szuwalski!

Description

Imagine that you are holding in your hands a special shipping box, one
that you can resize and rotate at will. You start with a large box and
randomly place all products into it. You rotate it so one corner points
towards the floor. The products will fall into this corner and form a
loose pile.

When they have stopped moving, you shrink the box as much as possible,
so each side touches the pile of products. Then you rotate the box so
another corner faces downwards.

You keep repeating these three steps (rotate, wait, and shrink) while
the box shrinks around ever tighter piles. At the end, you simply
measure the products' positions within the box.

This program simulates the entire process using rigid body dynamics:

  - instead of rotating the shipping box, the gravity vector is changed
  - the shipping box is always placed in the corner of the first octant,
    the three planes x==0, y==0, and z==0 form three sides of the
    shipping box and they never move
  - the other three sides of the box are planes x==C1, y==C2, z==C3,
    where the constants are found by determining the maximum x, y, and z
    coordinates among all products' corners
  - the shipping box never moves or rotates, only three sides of it are
    moved: tighter (closer to the origin) or looser (further away)
  - products are represented by a combination of bodies and geoms:
    bodies are points with mass and geoms have shape (used for collision
    detection), both share a position (the center of the box-shaped
    geom)
  - initial placement of the products is random
  - products are considered lying still when the bounding box of their
    most outward coordinates does not change for some time
  - global coordinates of products' corners are determined by first
    calculating their positions relative to the geom (using length,
    width, and height) and then transforming relative to global
    coordinates
  - when geoms collide, a temporary joint is added between them which
    resolves penetration, causing the geoms to bounce off each other
    and off the walls
  - the simulation goes through two phases: first the shrinking of the
    shipping box with low temporal resolution and high mass (higher
    speed, but allows more penetration), second a slight loosening of
    the shipping box with high temporal resolution and low mass (until
    all penetration is resolved)
  - the shrinking phase ends when shrinking fails for some time
  - the shrinking phase can be repeated (with new random placement of
    products) and the program keeps track of the shipping box with the
    minimal surface area seen so far
  - the loosening phase is only done once, at the end, for this minimum

Results

[rendering of an early result]  [rendering of a later result]
Solutions found for random N=100 input #58; left after 200 iterations with surface 100767 (+20.82%), right after 10000 iterations with surface 98117 (+17.64%).

You can paste your own input files and watch them get solved online within seconds (eight nodes with eight parallel processes each, not always available).

If you have a WebGL enabled browser, you can view three interactive examples: webgl-58, webgl-67, and webgl-92. Rotate, pan, and zoom by dragging the mouse while pressing mouse buttons.

Running the program with 20 iterations on a set of 100 randomly generated input files, the following results are observed:

# N lower_bound surface percent
1 21 37782.40 45677.10 20.90
2 55 53923.93 66931.08 24.12
3 45 45721.45 56909.28 24.47
4 74 68462.11 84810.88 23.88
5 97 83046.84 101588.70 22.33
6 88 73128.25 90770.97 24.13
7 4 11040.81 13281.28 20.29
...
99 48 42622.16 54123.19 26.98
100 97 84242.29 103193.38 22.50
A simple lower bound is based on the sum of volumes of inputs; in a perfect case, the output would be a cube with exactly the same volume.
The fifth column is defined as (surface - lower_bound) * 100.0 / lower_bound, i.e. how much larger, in percent, the output surface is than the lower bound.
$ ministat -C 5 results.txt
x results.txt
+------------------------------------------------------------------------------+
|                        x                                                     |
|                        x                                                     |
|                        x                                                     |
|                        x                                                     |
|                        x                                                     |
|                       xx                                                     |
|                       xx                                                     |
|                       xx                                                     |
|                       xxxx                                                   |
|                       xxxx                                                   |
|                      xxxxx                                                   |
|                      xxxxx                                                   |
|                      xxxxx                                                   |
|                      xxxxx                                                   |
|                     xxxxxx x                                                 |
|                     xxxxxxxx                                                 |
|                     xxxxxxxxx                                                |
|                     xxxxxxxxx                                                |
|                  x  xxxxxxxxxx                                               |
|x                xxxxxxxxxxxxxx      x                                       x|
|                  |_____MA_____|                                              |
+------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x 100          0.09         76.05         23.88       24.3778     6.3712948
Running the program with 10000 iterations on the same set of input files shows improved results:
$ ministat -C 5 results.txt results10000.txt
x results.txt
+ results10000.txt
+------------------------------------------------------------------------------+
|                   +                                                          |
|                   +                                                          |
|                   +                                                          |
|                   +                                                          |
|                   +                                                          |
|                   +                                                          |
|                   +                                                          |
|                   +                                                          |
|                   +                                                          |
|                   +                                                          |
|                   +                                                          |
|                   +                                                          |
|                   +                                                          |
|                   +                                                          |
|                   +                                                          |
|                  ++                                                          |
|                  ++    x                                                     |
|                  ++    x                                                     |
|                  ++    x                                                     |
|                  ++    x                                                     |
|                  ++    x                                                     |
|                  ++   xx                                                     |
|                  +++  xx                                                     |
|                  +++  xx                                                     |
|                  +++  xxxx                                                   |
|                  +++  xxxx                                                   |
|                  +++ xxxxx                                                   |
|                + +++ xxxxx                                                   |
|                + +++ xxxxx                                                   |
|                +++++ xxxxx                                                   |
|                +++++xxxxxx x                                                 |
|                +++++xxxxxxxx                                                 |
|                +++++xxxxxxxxx                                                |
|                +++++xxxxxxxxx                                                |
|            + + ++*++*xxxxxxxxx                                               |
|*       ++ ++++++*****xxxxxxxxx      x          +                            x|
|              |___AM__|_MA_____|                                              |
+------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x 100          0.09         76.05         23.88       24.3778     6.3712948
+ 100          0.09         47.32         18.43         17.87     4.0993298
Difference at 95.0% confidence
        -6.5078 +/- 1.48492
        -26.6956% +/- 6.09129%
        (Student's t, pooled s = 5.35714)

Source code

Building

This program depends on the open source library Open Dynamics Engine
(ODE) which is available under a BSD-style license, see

  http://www.ode.org/ode-license.html
  http://ode-wiki.org/wiki/index.php?title=Manual:_Introduction

Download the ODE source tarball from

  http://downloads.sourceforge.net/project/opende/ODE/0.13/ode-0.13.tar.bz2
  MD5 (ode-0.13.tar.bz2) = 04b32c9645c147e18caff7a597a19f84

and extract it in the same directory. The following steps can be used to
build (tested on Mac OS X 10.9.5, FreeBSD 8.4, and cygwin 1.7.28)

  $ tar zxf ode-0.13.tar.bz2
  $ ls
  CONTACT.txt             README.txt              ode-0.13.tar.bz2
  Makefile                ode-0.13                solve.cpp
  $ cd ode-0.13
  $ ./configure --disable-asserts --disable-threading-intf --disable-demos
  $ make
  $ cd ..
  $ make

On Linux you might have to install arc4random (tested on Ubuntu 12.04.3)

  apt-get install libbsd-dev
  add #include <bsd/stdlib.h> to solve.cpp
  add -lbsd to LDFLAGS in Makefile

Discussion

Academic papers

Prior art

Last updated on Tue May 23 12:48:44 2017 by daniel@benzedrine.ch.