World Records for the Problem of Packing Discs with Integer Radii

André Müller, Johannes Josef Schneider, Elmar Schömer

From time to time, Al Zimmermann and his coworkers organize programming contests on various optimization problems, for which the optimum solutions are unknown, with prizes given to those teams who send in the best solutions. The contest web page is located at www.recmath.org/contest.

From October 30, 2005 to January 14, 2006, Sam Byrd, Jean-Charles Meyrignac, and Al Zimmermann organized a contest on a specific problem of packing N circles with radii r_i=i, i=1, 2, …, N, in a circle with radius R in the way that the radius R is minimized and the circles do not overlap. The system sizes 5 ≤ N ≤ 50 were considered in the contest (see www.recmath.org/contest/CirclePacking). We heard of this contest shortly before it ended, started working on this type of problem, and were able to establish one world record for N=28, the solution of which was submitted by our student Tobias Baumann. After the end of the contest, we decided to continue working on this problem in order to generally develop and tune optimization algorithms for packing problems. We competed among each other for getting the best results. André Müller was the first to break some of the records established during the contest, then Elmar Schömer could establish a new world record for N=49. These records by André Müller and Elmar Schömer were beaten by Johannes Josef Schneider, who also managed to match all world records for 5 ≤ N ≤ 23 and N=25 and to beat the world records for all other values of N considered in the contest. He stopped creating new world records after having beaten himself for a few times for each instance. In 2011, Eckard Specht from the University of Magdeburg also considered this problem and was able to beat the world records for N=37, 45, and 50 created by Johannes Josef Schneider. Furthermore, he extended this problem to system sizes N ≤ 100, for which he also presents his best values on www.packomania.com.

Here you find a list of our world record configurations, which are given by the coordinates of the midpoints of the various circles. The midpoint of the circumcircle is supposed to lie at the origin:

N=24 R=75.7491426 (configuration)
N=26 R=84.9899391 (configuration)
N=27 R=89.7509627 (configuration)
N=28 R=94.5265365 (configuration)
N=29 R=99.4831116 (configuration)
N=30 R=104.5411690 (configuration)
N=31 R=109.6824564 (configuration)
N=32 R=114.8409490 (configuration)
N=33 R=120.0658465 (configuration)
N=34 R=125.3669392 (configuration)
N=35 R=130.9176279 (configuration)
N=36 R=136.4922446 (configuration)
N=37 R=142.0513754 (configuration)
N=38 R=147.4568453 (configuration)
N=39 R=153.3800827 (configuration)
N=40 R=159.1824078 (configuration)
N=41 R=165.0369006 (configuration)
N=42 R=170.8953274 (configuration)
N=43 R=177.0513747 (configuration)
N=44 R=183.0992248 (configuration)
N=45 R=189.2029320 (configuration)
N=46 R=195.5264351 (configuration)
N=47 R=201.7279256 (configuration)
N=48 R=208.0901593 (configuration)
N=49 R=214.2954475 (configuration)
N=50 R=220.6004187 (configuration)

Our configuration for N=50 in shown in the picture above. What the other solutions look like, you can see both in this pdf file, with numbers in the circles denoting their radii, or in a multi-color version. (By clicking on the system sizes, you get corresponding images with higher resolution) We describe our optimization approach based on the physical general-purpose algorithm simulated annealing and an afterburner based on local optimization ideas from computer science in a scientific paper in the journal Physical Review E . There you can also find additional results on the dynamics of the optimization process, on similarities and differences between various quasi optimum configurations, and on scaling laws for the optimum values of this problem.