Combination of physical algorithms and methods from computer science for the optimization of geometric packing problems

The aim of our project is to develop a high performance algorithm for the optimization of packing problems. Most of these problems are so complex that no exact mathematical optimization algorithms exist. Thus, we intend to develop a heuristic method, combining common optimization methods from physics and computer science and adjusting them to this kind of problem. We focus on geometric packing problems, for which the coordinates of the objects to be packed exhibit continuous values, thus forcing us to combine global optimization algorithms, like simulated annealing, with local methods, like gradient descent.

The first problem we considered was a task defined in an international contest: disks of various sizes had to be packed in a circumcircle of minimum radius. We were able to beat or to match all world records, which had been established during the contest by 155 groups from 32 countries competing. Thus, we proved the superiority of our new algorithm to existing methods.

Now we plan to study further packing problems from physics and computer science by means of our new algorithm. We intend to consider bidisperse systems of colloidal particles with various radii and to determine their optimum allocation under constraints, like confinement. On the other hand, we consider problems from computer science and mathematics, like the kissing number problem, in which the maximum number of equally large spheres in D dimensions, which touch a sphere in their midst, has to be found.

View image in original size
View image in original size photo: Johannes Schneider
World record for a dense packing of 50 disks with various sizes

Zum Inhalt der Seite springen Zur Navigation der Seite springen