AM Packing Benchmarks

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

See the inventory list below for an overview of all benchmarks, tables, symbols used, etc.

Packing-Related Links

• Eckard Specht's excellent packing benchmarks site: Lots of nice pictures, shortest tours of the items and a contact analysis for each packing; uses a different file format and normalizes most of the container sizes to 1. Some of my solutions are also listed there.

• Erich's Packing Center

• an industrial application of circle packing with constraints

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,300,400,600,800,1000,2000 | "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