Skip to content

Latest commit

 

History

History
305 lines (257 loc) · 15.3 KB

README.md

File metadata and controls

305 lines (257 loc) · 15.3 KB
Raw

AM Packing Benchmarks

This repository contains my personal (putative/quasi-optimum) solutions for many packing problem benchmark instances.

Some of the solutions are also listed on Eckard Specht's excellent website www.packomania.com. He has nice pictures, shortest tours of the items and a contact analysis for each packing. Note that he uses a different file format and normalizes most of the container sizes to 1.

You should also have a look at http://www2.stetson.edu/~efriedma/packing.html.

See below for a list of all benchmarks, tables of all the symbols used, etc.

Repository Structure

container_type 
    scenario_type
        {overview images}
        {benchmark result lists}
        item_shape_distribution
            {result packing files}

Conventions

  • items : objects to be packed
  • container : object(s) enclosing the items
  • n : number of items
  • i : item index in range [1,n]
  • i = 0 : container index
  • Containers are centered at the global origin and aligned to the coordinate system axes.
  • Symbols referring to container properties start with an uppercase letter.

Scenario / Folder Names

  • find smallest container for a set of items: "min-ContainerType(ItemType)"
  • find legal arrangement of items in a rigid container: "ContainerType(ItemType)"

Inventory

Scenario Description
min-Circle(Circle) circles in smallest enclosing circle
min-Circle(ConvexRegularPolygon) convex regular polygon in smallest enclosing circle
min-Square(Circle) circles in smallest enclosing square
min-Square(Square) freely rotatable squares in smallest enclosing square
min-Square(ConvexRegularPolygon) convex regular polygon in smallest enclosing square
min-Rectangle(Circle) circles in smallest enclosing rectangle
min-Rectangle(RectangleAA) axis-oriented rectangles in smallest enclosing rectangle
min-Rectangle(Rectangle) freely rotatable rectangles in smallest enclosing rectangle
min-Sphere(Sphere) spheres in smallest enclosing sphere
min-Cube(Sphere) spheres in smallest enclosing cube
min-Cuboid(Sphere) spheres in smallest enclosing cuboid
min-Cube(Cube) cubes in smallest enclosing cube
min-Cube(CubeAA) axis-aligned cubes in smallest enclosing cube
min-Cuboid(Cuboid) cuboids in smallest cuboid
min-Sphere4d(Sphere4d) 4d hyperspheres in smallest enclosing 4d hypersphere
min-Sphere5d(Sphere5d) 5d hyperspheres in smallest enclosing 5d hypersphere

2D Benchmark Instances

Container Type Item Type Item Shape Distribution n
min-Circle Circle r(i) = 1 1 - 600
min-Circle Circle r(i) = i 1 - 200 "Al Zimmermann's contest set"
min-Circle Circle r(i) = i ^ (+1/2) 5 - 100
min-Circle Circle r(i) = i ^ (-1/2) 5 - 100
min-Circle Circle r(i) = i ^ (-2/3) 5 - 100
min-Circle Circle r(i) = i ^ (-1/5) 5 - 100
min-Circle RegularTriangle r(i) = 1 2 - 100
min-Circle RegularTriangle r(i) = i 2 - 100
min-Circle RegularPentagon r(i) = 1 2 - 100
min-Circle RegularPentagon r(i) = i 2 - 100
min-Circle RegularHexagon r(i) = 1 2 - 100
min-Circle RegularHexagon r(i) = i 2 - 100
min-Circle RegularOctagon r(i) = 1 2 - 100
min-Circle RegularOctagon r(i) = i 2 - 100
min-Square Circle r(i) = 1 1 - 100
min-Square Circle r(i) = i 1 - 100
min-Square Circle r(i) = i ^ (+1/2) 5 - 100
min-Square Circle r(i) = i ^ (-1/2) 5 - 100
min-Square Square h(i) = 1 1 - 100
min-Square Square h(i) = i 1 - 100
min-Square RegularTriangle r(i) = 1 2 - 100
min-Square RegularTriangle r(i) = i 2 - 100
min-Square RegularPentagon r(i) = 1 2 - 100
min-Square RegularPentagon r(i) = i 2 - 100
min-Square RegularHexagon r(i) = 1 2 - 100
min-Square RegularHexagon r(i) = i 2 - 100
min-Square RegularOctagon r(i) = 1 2 - 100
min-Square RegularOctagon r(i) = i 2 - 100
min-Rectangle Circle r(i) = 1 1 - 100
min-Rectangle Circle r(i) = i 1 - 100
min-Rectangle RetangleAA hx(i)=i, hy(i)=0.750·i 1 - 100
min-Rectangle RetangleAA hx(i)=i, hy(i)=0.500·i 1 - 100
min-Rectangle RetangleAA hx(i)=i, hy(i)=0.250·i 1 - 100
min-Rectangle RetangleAA hx(i)=i, hy(i)=0.125·i 1 - 100
min-Rectangle Rectangle hx(i)=i, hy(i)=0.750·i 1 - 100
min-Rectangle Rectangle hx(i)=i, hy(i)=0.500·i 1 - 100
min-Rectangle Rectangle hx(i)=i, hy(i)=0.250·i 1 - 100
min-Rectangle Rectangle hx(i)=i, hy(i)=0.125·i 1 - 100

3D Benchmark Instances

Container Type Item Type Item Shape Distribution n
min-Sphere Sphere r(i) = 1 1 - 100
min-Sphere Sphere r(i) = i 1 - 100
min-Cube Sphere r(i) = 1 1 - 100
min-Cube Sphere r(i) = i 1 - 100
min-Cube Cube h(i) = 1 1 - 100
min-Cube Cube h(i) = i 1 - 100
min-Cube CubeAA h(i) = 1 1 - 100
min-Cube CubeAA h(i) = i 1 - 100
min-Cuboid Sphere r(i) = 1 1 - 100
min-Cuboid Sphere r(i) = i 1 - 100
min-Cuboid Cuboid hx(i)=i, hy(i)=0.75·i, hz(i)=0.5·i 2 - 100 "boxes" 4 x 3 x 2
min-Cuboid Cuboid hx(i)=i, hy(i)=0.5·i, hz(i)=0.25·i 2 - 100 "bricks" 4 x 2 x 1
min-Cuboid Cuboid hx(i)=i, hy(i)=0.5·i, hz(i)=0.1·i 2 - 100 "plates" 10 x 5 x 1
min-Cuboid Cuboid hx(i)=i, hy(i)=0.125·i, hz(i)=0.125·i 2 - 100 "poles" 8 x 1 x 1
min-Cuboid Cuboid AM cuboid set 1 2 - 100

4D & 5D Benchmark Instances

Container Type Item Type Item Shape Distribution n
min-Sphere4d Sphere4d r(i) = i 10, 20, 30, 40, 50, 100
min-Sphere5d Sphere5d r(i) = i 10, 20, 30, 40, 50, 100

File Format

  • the encoding is ASCII, multibyte characters must not be used
  • line endings are expected to be LF only
  • whitespace apart from LF does not have any semantic meaning other than separating numbers or identifier texts

Packing File Format (.pac)

#PACKING
#CONTAINER
  <entity-type>
  1
  <container entity-specification>
#CONTENT
   <entity-type>
   <number of items n>
   <item 1 entity-specification>
   <item 2 entity-specification>
   ...
   <item n entity-specification>

Packing Input File Format (.shp)

<entity-type>
<number of entities n>
<entity-specification 1>
<entity-specification 2>
...
<entity-specification n>

Entity Specification

  • entity-specification : shape-specification placing
  • placing : position orientation scaling
  • position : center coordinates x, y, z, a, b, ...
  • orientation : angle between local and global x-axis or unit quaternion
  • scaling : scaling factors sx, sy, sz, sa, sb, ...

Shape Specification

symbol description
r radius
h half length
l full length
hx half length on axis x
lx full length on axis x

Shape Placing

symbol description
x, y, z, ... x,y,z...-coordinate of the local origin
p angle(local x, global x), counter-clockwise in radians
qw qx qy qz orientation unit quaternion (qw: scalar part)
sx, sy, sz, ... scaling along x,y,z...-axis

Simple 2D Entity Types

type description specification
Circle circle r x y
SquareAA axis-aligned square h x y
Square freely rotatable square h x y p
RectangleAA axis-aligned rectangle hx hy x y
Rectangle freely rotatable rectangle hx hy x y p
RegularTriangle freely rotatable regular triangle r x y p
RegularPentagon freely rotatable regular pentagon r x y p
RegularHexagon freely rotatable regular hexagon r x y p
RegularOctagon freely rotatable regular octagon r x y p
Capsule2d rectangle with semicircular caps r h x y p

Simple 3D Entity Types

type description specification
Sphere sphere r x y z
CubeAA axis-aligned cube h x y z
Cube freely rotatable cube h x y z qw qx qy qz
CuboidAA axis-aligned cuboid hx hy hz x y z
Cuboid freely rotatable cuboid hx hy hz x y z qw qx qy qz
RegularTetrahedron regular tetrahedron r x y z qw qx qy qz
Capsule cylinder with hemispherical caps r h x y z qw qx qy qz

Simple Entity Types (more than 3 dimensions)

type description specification
HyperSphere4d 4-dimensional sphere r x y z a
HyperSphere5d 5-dimensional sphere r x y z a b

Complex Entity Types

  • Polygon: planar, closed and possibly non-convex polygon with m points and m edges (orientation: ccw)

    <number of points m>
<point 1>
<point 2>
...
<point m>
x y  p

  • TriangleCompound: collection of triangles "triangle soup"

    <number of triangles m>
<point 1-a> <point 1-b> <point 1-c>
<point 2-a> <point 2-b> <point 2-c>
...
<point m-a> <point m-b> <point m-c>
x y z  qw qx qy qz

Special Entity Types

type description specification
$file name of .shp file filename
$file // $placing name of .shp file and transformation filename // placing

Examples

  • A packing solution file for the min-Circle(Circle) problem:

    #PACKING
#CONTAINER
Circle
1
5  0 0
#CONTENT
Circle
3
1  1 3
2  3 0
3  -2 0

  • A packing file that references 3 .shp files containing some polygons:

    #PACKING
#CONTAINER
RectangleAA
1
100 200 0 0
#CONTENT
$file // $placing
3
singlePolygon1.shp // -10.5 6.7  12.34
singlePolygon2.shp // 0.0 0.0    10
manyPolygons.shp   // 12.4 -23   270

  • A .shp file specifying two 4-sided polygons:

    Polygon
2
4
0.0 0.0
5.0 0.0
5.0 4.0
6.0 0.0
  1.023 -0.34
4
0.0 0.0
5.0 0.0
5.0 5.0
5.0 0.0
  -12.2 4.5