Starting to experiment with combinatorial packings by gluing particles together along their edges and finding a configuration with maximal ratio between the volume of the sum of the particles and the volume of the convex hull of the particles. Here are some examples.

ratio = 0.4500

Expanding the tree to two particles. There are only two admissible configurations with different  ratios for two particles.

1. branch

ratio = 0.4

Ratios from left to right: 0.3857,  0.4045,  04075, 0.4372,  0.4015,  0.3724

 

2. branch

ratio = 0.4091

Ratios from left to right: 0.4045,  0.3971, 0.3803, 0.4075,  0.4372,  0.4015

Just to have everything in one place.

MiloslavTorda_FirstYearReport.pdf

I modified the original algorithm to work better. It’s significantly slower but I get better results. There seems to be a relationship between number of objects in the unit cell and the algorithm’s performance. The  more shapes the worse density. (more local minima on the landscape?). The other thing is packings are physically unrealistic, that is the shapes from different unit cells are intertwined. No more problem is that the density did go higher then 1 which should not be.  Maybe we need a more suitable formula for computing density in the periodic setting.

Results

1 pentacene model in a unit cell

Density = 1.9932

 

2 pentacene models in a unit cell

Density = 1.0063

4 pentacene models in a unit cell

Density = 0.8093

8 pentacene models in a unit cell

Density = 0.6940

54 pentacene models in a unit cell

Density = 0.1788

I got to packing Pentacene model  based on previous computations. see http://milotorda.net/index.php/pentacene-modeling/    . From the coordinates of the atoms of the Pentacene molecule

I have created a point cloud by placing 14 points around every atom in the Pentacene uniformly placed on a sphere with radius 0.5573/2.

and finally taken the convex hull of the point cloud as the 3D-model of Pentacene. The resulting structure is in the form of triangulation with 58 vertices, 112 edges and 168 faces. Volume of the polyhedron is 48.237.

Subsequently I used the Torquato – Jiao packing algorithm to create packings of various numbers of pentacene models in a unit cell.

4 pentacene models in a unit cell

Initial configuration

Density = 0.0037.

Original algorithm

First iteration

Density = 0.0291

Second iteration

Density = 0.0512

simulated annealing

First iteration

Density = 0.0514

Second iteration

Density = 0.1178

8 pentacene models in a unit cell

initial configuration

Density = 0.0075

Original algorithm

First iteration

Density = 0.0660

Second iteration

Density = 0.0436

simulated annealing

First iteration

Density = 0.0234

I experimented with the packing of triangles using previous model and Matlab’s fmincon() optimizer. For each setting 100 runs were performed with the following initial conditions. Triangles have  the same initial positions in the initial unit cell with random rotations. The algorithm used was interior point with supplied objective gradient.

3 triangle setting

Out of 100 runs 45 resulted in feasible solutions. 40 with exitflag== -2, 0 with exitflag== -1, 21 with exitflag== 0., 0 with exitflag== 1,  39 with exitflag== 2.  Mean density in the feasible solution cases was 0.5827 and variance 0.0197. The best case had density 0.8118.

Left is the initial setup and right is the best found solution.

 

4 triangle setting

Out of 100 runs 20 resulted in feasible solutions. 66 with exitflag== -2, 0 with exitflag== -1,  14 with exitflag== 0., 0 with exitflag== 1,  20 with exitflag== 2.  Mean density in the feasible solution cases was 0.5850 and variance  0.0127. The best case had density  0.7959.

Left is the initial setup and right is the best found solution.

5 triangle setting

Out of 100 runs 9 resulted in feasible solutions. 71 with exitflag== -2, 0 with exitflag== -1,  20 with exitflag== 0., 0 with exitflag== 1,  9 with exitflag== 2.  Mean density in the feasible solution cases was 0.5637 and variance  0.0111. The best case had density  0.7246.

Left is the initial setup and right is the best found solution.

 

4 triangle setting and GA

I did similiar thing with the GA algorithm. Out of 49 runs 19 resulted in feasible solutions.  Mean density in the feasible solution cases was 0.7667 and variance  0.0115. The best case had density  0.9230.

I used matlab global optimization toolbox’s genetic algorithm to solve the triangle packing problem outlined in previous post. It does what it is supposed to do :). i.e finds a tiling.

Left output of the GA algorithm. Optimal packing of two congruent triangles (red) and unit cell (blue). On the right are surrounding unit cells added.

Same but with 3 triangles in a unit cell. Doesn’t  work so well. Takes 194 sec to compute. Density is 0.7178.

4 triangles. Took 138.315 sec to compute. Density is 0.6715;

5 triangles took 829.64 sec to compute. Density is 0.8055.

6 triangles took 228.458 sec to compute. Density is 0.7534.

I’ve equipped the packing algorithm with simulated annealing schedule and used it to pack 8 octahedra in a unit cell. Here are some pictures from one run.

Left is the initial packing and right final packing.

27 unit cells of the above packings.

Initial density is 0.1667. The final density is 0.9178. Optimal lattice packing density is 0.9474 (a result by Minkowski) which is hypothesised to be general optimal packing.

I ran also the algorithm without the simulated annealing with same parameters and the final density was 0.8281. Now the question is if the simulated annealing schedule is an improvement or this was achieved just by chance.

Did some exploration of the parameter space of the packing algorithm for comparison of the C++ a Julia versions. Moved values of one parameter and fixed all others to the same values.  10 iterations for every parameter were done and collected densities of resulting packing configurations of 8 tetrahedra. The initial configuration of tetrahedra were same in all cases.

 

 

The initial density was 0.06415. The best I got from the experiments was 0.67045. Below are the visualizations of the packings.

Left initial packing of 8 tetrahedra in a unit cell and right best packing achieved.

Left 27 unit cell of the initial packing. Right 27 unit cells of the best achieved packing.

It’s been a while since last post.

I’ve got hold of the polyhedra packing algorithm from Dense packings of the Platonic and Archimedean solids (thank you Yang) in C++ and rewritten it in Julia.

Here are the images from the first experiments of packing 8 tetrahedra in a unit cell.

Left is the initial configuration and right is the configuration after 1000 iterations.

 

The initial density is 0.06415 and and the density after 1000 iterations is 0.58888. For comparison the densest lattice packing of tetrahedra is 0.36735 but the densest found packing in the Nature paper is 0.82264.