Disk Packing in a Square: A New Global Optimization Approach

INFORMS Journal on Computing · 2008 · Volume 20 · Issue 4

Abstract

We present a new computational approach to the problem of placing n identical nonoverlapping disks in the unit square in such a way that their radii are maximized. The problem has been studied in a large number of papers, from both a theoretical and a computational point of view. In this paper, we conjecture that the problem possesses a so-called funneling landscape, a feature that is commonly found in molecular conformation problems. Based on this conjecture, we develop a stochastic search algorithm that displays excellent numerical performance. Thanks to this algorithm, we could improve over previously known putative optima in the range n ≤ 130 in as many as 32 instances, the smallest of which is n = 53.

Keywords

disk packing, circle packing, continuous dispersion problem, basin hopping, global optimization, stochastic methods

Enable JavaScript for citation tools and additional paper interactions.