Optimization Online


Disk Packing in a Square: A New Global Optimization Approach

Bernardetta Addis (b.addis***at***ing.unifi.it)
Marco Locatelli (locatell***at***di.unito.it)
Fabio Schoen (schoen***at***ing.unifi.it)

Abstract: 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.

Keywords: disk packing, circle packing, sphere packing, basin hopping, global optimization, stochastic methods

Category 1: Global Optimization

Category 2: Global Optimization (Stochastic Approaches )


Download: [PDF]

Entry Submitted: 10/12/2005
Entry Accepted: 10/12/2005
Entry Last Modified: 10/14/2005

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society