Efficiently packing unequal disks in a circle: a computational approach which exploits the continuous and combinatorial structure of the problem

B. Addis (b.addising.unifi.it)
M. Locatelli (locatelldi.unito.it)
F. Schoen (fabio.schoenunifi.it)

Abstract: Placing $N$ non-overlapping circles in a smallest container is a well known, widely studied problem that can be easily formulated as a mathematical programming model. Solving this problem is notoriously extremely hard. Recently a public contest has been held for finding putative optimal solutions to a special case in circle packing. The contest saw the participation of 155 teams who submitted a total of $27\,490$ tentative solutions. In this paper we will explain the strategy we used for attacking this problem. The main aim of the paper is to show how we could win the competition with relatively little computational power, by properly mixing local and global optimization strategies with random search and local moves. The main lesson learnt in participating to this context has been that although computational power surely helps, it is not strictly necessary, and clever utilization of relatively standard ideas from global optimization can beat special purpose methods.

Keywords: global optimization, basin-hopping, circle packing, local moves, population-based approaches

Category 1: Global Optimization

Citation:

Download: [PDF]

Entry Submitted: 03/07/2006
Entry Accepted: 03/09/2006
Entry Last Modified: 03/13/2006

Modify/Update this entry