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

Bernardetta Addis (b.addising.unifi.it)
Marco Locatelli (locatelldi.unito.it)
Fabio Schoen (schoening.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