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 contine working on this problem in order to generally develop and tune optimization algorithms for packing problems. In the mean time, we were able to match all world records for 5 ≤ N ≤ 23 and N=25. Furthermore, we succeeded in finding new world record configurations for all other values of N considered in the contest.

Here you find a list of the 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)

The new world record 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.