Disk Packing in a Square: A New Global Optimization Approach

Disk Packing in a Square: A New Global Optimization Approach

0.00 Avg rating0 Votes
Article ID: iaor200952633
Country: United States
Volume: 20
Issue: 4
Start Page Number: 516
End Page Number: 524
Publication Date: Sep 2008
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: heuristics
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.

Reviews

Required fields are marked *. Your email address will not be published.