Disk Packing in a Square: A New Global Optimization Approach

We present a new computational approach to the problem of placing $n$ identical non overlapping disks in the unit square in such a way that their radius is maximized. The problem has been studied in a large number of papers, both from a theoretical and from a computational point of view. In this paper we conjecture that the problem possesses a so-called funneling landscape, a feature which is commonly found in molecular conformation problems. Based upon this conjecture we develop a stochastic search algorithm which displays excellent numerical performance. Thanks to this algorithm we could improve over previously known putative optima in the range $n \leq 130$ in as many as 32 instances, the smallest of which is $n=53$. First experiments in the related problem of packing equal spheres in the unit cube led us to an improvement for $n=28$ spheres.

Article

Download

View Disk Packing in a Square: A New Global Optimization Approach