Optimization Online


Packing circles in a square: new putative optima obtained via global optimization

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

Abstract: The problem of finding the optimal placement of $N$ identical, non overlapping, circles with maximum radius in the unit square is a well known challenge both in classical geometry and in optimization. A database of putative optima is currently maintained at \url{www.packomania.com}. Recently, through clever use of an extremely simple global optimization method, we succeeded in finding improved configurations for several instances. The improved configurations are in the range $N \leq 90$, i.e., they improve even over relatively small instances (even $N=53$), an event that some researchers did not believe to be possible. We also improved larger instances using a simpler strategy initialized at the previously known putative optimum.

Keywords: circle packing, basin hopping, global optimization

Category 1: Global Optimization

Category 2: Global Optimization (Stochastic Approaches )

Category 3: Global Optimization (Applications )

Citation: DSI report 01/2005 Dipartimento di Sistemi e Informatica Universita' di Firenze

Download: [PDF]

Entry Submitted: 03/04/2005
Entry Accepted: 03/04/2005
Entry Last Modified: 03/07/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