A novel packing heuristic based on rigid body simulation

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html> <head> <meta name="description" content="A novel packing heuristic based on rigid body simulation"> <meta name="keywords" content="vistaprint, bin packing, non-orthogonal packing, open dimension problem, heuristic, rigid body dynamics, solid body dynamics, simulation"> <meta name="author" content="Daniel Hartmeier"> <meta name="robots" content="index, follow"> <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> <link rel="canonical" href="https://www.benzedrine.ch/3D-ODRPP.html"> <title>A novel packing heuristic based on rigid body simulation</title> </head> <body text="#000000" bgcolor="#FFFFFF" link="#1919C0" vlink="#101030" alink="#FE0000"> <table width="100%"><tr><td> <table><tr><td valign=top height="62"> <img src="/logo.jpg" alt="[benzedrine.ch logo]"><br> </td></tr></table> </td></tr><tr><td> <table> <tr><td valign=top> <table cellspacing=2 cellpadding=1 border=0 width=175> <tr><td bgcolor="#C8C8FF" align=center><b>Contents</b></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/index.html">Home</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/dhartmei.html">Daniel Hartmeier</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/pf.html">Packet Filter</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/pfstat.html">pfstat</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/mailinglist.html">Mailing list</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/relaydb.html">Annoying spammers</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/ackpri.html">Prioritizing ACKs</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/transquid.html">Transparent squid</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/icbirc.html">Proxy ICB/IRC</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/milter-regex.html">milter-regex</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/milter-spamd.html">milter-spamd</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/milter-checkrcpt.html">milter-checkrcpt</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/yubikey.html">login_yubikey</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/dorabella.html">Dorabella</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/tron.html">Tron</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/planetwars.html">Planet Wars</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/hexiom.html">Hexiom solver</a></td></tr> <tr><td bgcolor="#E0E0FF"><a href="/3D-ODRPP.html">3D-ODRPP</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/polygon-partition.html">Polygon partition</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/grid-puzzle.html">Mikero's grid puzzle</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/darkstar.html">Dark Star</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/misc.html">Misc</a></td></tr> <tr><td bgcolor="#F0F0FF"><a href="/statistics.html">Statistics</a></td></tr> </table><br> </td><td valign=top> <table width=25><tr><td><br></td></tr></table> </td><td valign=top bgcolor="#F0F0FF" width="100%">  <h2>A novel packing heuristic based on rigid body simulation</h2> The <a href="http://lifeinvistaprint.com/technology/tech-challenge-2014/">Vistaprint Tech Challenge 2014</a> (<a href="https://archive.is/LyQoM">archived details</a>) asked:<p> <i> 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? </i><p> This is a <a href="https://en.wikipedia.org/wiki/Packing_problem">packing problem</a>. According to the typology it is a three-dimensional rectangular <b>open dimension problem</b> (ODP) with three variable dimensions.<br> Notably, it allows <b>arbitrary, non-orthogonal rotations</b>, and the target is <b>low surface area</b>.<p> Such problems are <a href="https://en.wikipedia.org/wiki/Np-complete">NP-complete</a>, and N=100 is a non-trivial size.<br> Hence, guaranteed optimal solutions are out of reach, instead a good <a href="https://en.wikipedia.org/wiki/Heuristic_%28computer_science%29">heuristic</a> is sought.<br> 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.<p> In a novel approach, a heuristic algorithm based on solid body dynamics was written in ~350 lines of C++ using the <a href="http://www.ode.org/">Open Dynamics Engine</a> (ODE) library.<br> Interestingly, the implementation is <a href="https://en.wikipedia.org/wiki/Embarrassingly_parallel">embarrasingly parallel</a>, and the quality of the result increases with parallel runs (<a href="https://en.wikipedia.org/wiki/Monte_Carlo_method">Monte Carlo method</a>).<br> Submitted October 13th 2014, results <a href="http://lifeinvistaprint.com/technology/vistaprint-tech-challenge-winner-2014/">announced</a> (<a href="https://archive.is/q0t6S">archive</a>) December 3rd 2014. Congratulations to <a href="https://github.com/zuwalski/vistaPickPack">Lars Szuwalski</a>!<p> <h3>Description</h3> <pre> 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 </pre> <h3>Results</h3> <img src="vistaprint/N100-small.jpg" width="630px" height="550px" alt="[rendering of an early result]">  <img src="vistaprint/N100-small2.jpg" width="630px" height="550px" alt="[rendering of a later result]"><br> <small>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%). </small><p> You can paste your own input files and watch them get <a href="http://3d-odrpp.nova.swisscloud.io">solved online</a> within seconds (eight nodes with eight parallel processes each, not always available).<p> If you have a <a href="https://en.wikipedia.org/wiki/Webgl">WebGL</a> enabled browser, you can view three interactive examples: <a href="/vistaprint/webgl-58.html">webgl-58</a>, <a href="/vistaprint/webgl-67.html">webgl-67</a>, and <a href="/vistaprint/webgl-92.html">webgl-92</a>. Rotate, pan, and zoom by dragging the mouse while pressing mouse buttons.<p> Running the program with 20 iterations on a set of 100 randomly generated <a href="vistaprint/in.tgz">input files</a>, the following <a href="vistaprint/results.txt">results</a> are observed: <pre> # 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 </pre> A simple lower bound is based on the sum of volumes of inputs; in <a href="https://en.wikipedia.org/wiki/Conway_puzzle">a perfect case</a>, the output would be a cube with exactly the same volume.<br> The fifth column is defined as <i>(surface - lower_bound) * 100.0 / lower_bound</i>, i.e. how much larger, in percent, the output surface is than the lower bound. <pre> $ <a href="https://www.freebsd.org/cgi/man.cgi?query=ministat">ministat</a> -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 </pre> Running the program with 10000 iterations on the same set of input files shows improved <a href="vistaprint/results10000.txt">results</a>: <pre> $ 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) </pre> <h3>Source code</h3> <ul> <li><a href="vistaprint/Makefile">Makefile</a><br> <li><a href="vistaprint/random.c">random.c</a> produce random input<br> <li><a href="vistaprint/solve.cpp">solve.cpp</a> find a solution (two minutes on a single CPU core)<br> <li><a href="vistaprint/verify.cpp">verify.cpp</a> verify output<br> <li><a href="vistaprint/webgl.cpp">webgl.cpp</a> render output as WebGL page (example: <a href="/vistaprint/webgl-58.html">webgl-58</a>)<br> <li><a href="vistaprint/webgl-template.html">webgl-template.html</a> HTML template for the above program, uses <a href="http://threejs.org/">three.js</a><br> </ul><p> <h3>Building</h3> <pre> This program depends on the open source library Open Dynamics Engine (ODE) which is available under a BSD-style license, see <a href="http://www.ode.org/ode-license.html">http://www.ode.org/ode-license.html</a> <a href="http://ode-wiki.org/wiki/index.php?title=Manual:_Introduction">http://ode-wiki.org/wiki/index.php?title=Manual:_Introduction</a> Download the ODE source tarball from <a href="http://downloads.sourceforge.net/project/opende/ODE/0.13/ode-0.13.tar.bz2">http://downloads.sourceforge.net/project/opende/ODE/0.13/ode-0.13.tar.bz2</a> 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 </pre><p> <h3>Discussion</h3> <ul> <li><a href="https://www.reddit.com/r/programming/comments/2i6z6y/10k_programming_challenge_by_vistaprint/">$10k Programming Challenge by Vistaprint</a> discussion on reddit.com<br> <li><a href="http://www.i-programmer.info/news/204-challenges/7829-10k-contest-to-solve-a-problem-worth-millions.html">$10K Contest To Solve A Problem Worth Millions</a> article by Alex Armstrong on i-programmer.info<br> <li><a href="http://arstechnica.com/civis/viewtopic.php?f=20&start=7120&t=1159182">while (true) {</a> discussion on arstechnica.com forum (scroll down and see subsequent pages)<br> </ul><p> <h3>Academic papers</h3> <ul> <li><a href="http://www.mansci.ovgu.de/mansci_media/publikationen/2007/typology-EGOTEC-5t0pvr6fjifln4r4oav60tt612.pdf">An improved typology of cutting and packing problems</a> by Gerhard Waescher, Heike Haussner, Holger Schumann<br> <li><a href="http://www.diku.dk/hjemmesider/ansatte/jegeblad/phd.pdf">Heuristics for Multidimensional Packing Problems</a> by Jens Egeblad <li><a href="http://www98.griffith.edu.au/dspace/bitstream/handle/10072/34843/64978_1.pdf">Three Dimensional Bin Packing Problem with Variable Bin Height</a> by Yong Wu, Wenkai Li, Mark Goh, Robert de Souza<br> <li><a href="http://www.researchgate.net/publication/2353632_The_Three-Dimensional_Bin_Packing_Problem/file/79e4150c0a70c179a9.pdf">The Three-Dimensional Bin Packing Problem</a> by Silvano Martello, David Pisinger, Daniele Vigo<br> <li><a href="http://www.tandfonline.com/doi/abs/10.1080/02331934.2013.877906">A global optimization approach for solving three-dimensional open dimension rectangular packing problems</a> by Jung-Fa Tsaia, Pei-Chun Wanga & Ming-Hua Lin<br> <li><a href="http://scm.snu.ac.kr/publication/paper/61.pdf">A hybrid genetic algorithm with a new packing strategy for the three-dimensional bin packing problem</a> by Kyungdaw Kang, Ilkyeong Moon, Hongfeng Wang<br> <li><a href="http://www1.dem.ist.utl.pt/engopt2010/Book_and_CD/Papers_CD_Final_Version/pdf/06/01106-01.pdf">On the three-dimensional bin packing using rotations</a> by Ana Maria de Almeida and Marisa Figueiredo<br> <li><a href="http://isiarticles.com/bundles/Article/pre/pdf/8153.pdf">A biased random key genetic algorithm for 2D and 3D bin packing problems</a> by Jose Fernando Goncalves, Mauricio G.C. Resende<br> <li><a href="http://www.icita.org/2010/papers/16-ru-Abramov.pdf">Decision Support Systems in Transport Logistics</a> by A. L. Abramov, A. A. Kovtaniuk<br> <li><a href="http://www.researchgate.net/profile/Eric_Lutters/publication/257745425_3D_Nesting_of_Complex_Shapes/links/004635285236e2abe4000000?origin=publication_detail">3D Nesting of Complex Shapes</a> by E. Lutters, D. ten Dam, T. Faneker<br> </ul><p> <h3>Prior art</h3> <ul> <li><a href="https://www.youtube.com/watch?v=39ihvsGr-Do">Simulation of meshed gummybears using the Discrete Element Method</a><br> <li><a href="https://www.youtube.com/watch?v=JHZuiv3Eg3A">Vibration packing</a><br> <li><a href="https://www.youtube.com/watch?v=bRm4sB97G5A">cube packing with stress waves</a><br> <li><a href="https://en.wikipedia.org/wiki/Defensive_publication">Defensive publication</a>: <a href="https://archive.is/FLQFH">https://archive.is/FLQFH</a><p> </ul><p>  </td></tr> </table> </td></tr><tr><td> <center> <small> Last updated on Tue Sep 26 08:57:43 2017 by <a href="mailto:daniel@benzedrine.ch">daniel@benzedrine.ch</a><a href="/crawlertrap/index.html?no-prefetch">.</a><br><br> </small> </center> </td></tr> </table> </body> </html>

CINXE.COM

A novel packing heuristic based on rigid body simulation