Circle Packing Challenge Activity

Challenge Problem in Global Optimization

Determine the minimum circumscribing radius for n circles with radius i^(-0.5) for i=1..n.


Background

Packing problems are a class of optimization problems in mathematics which involve attempting to pack objects together (often inside a container), as densely as possible. Many of these problems can be related to real life packaging, storage and transportation issues. In a packing problem, you are given:

  • 'containers' - in this case a circle that circumscribes all of the other circles
  • 'goods' (usually a single type of shape), some or all of which must be packed into this container

Usually the packing must be without overlaps between goods and other goods or the container walls. The aim is to find the configuration with the maximal density. In some variants the overlapping (of goods with each other and/or with the boundary of the container) is allowed but should be minimized.


Download Sample MATLAB Code

MATLAB source code writes an APM optimization file and sends it to the APMonitor server for solution. After the script executes, a figure appears that shows the best and worst configurations.


Download Sample Python Code - Version 1

Python source code re-writes the optimization file and sends it to the APM server for solution. After the script executes, a figure appears that shows the configuration that was produced.


Example Solution for 4 Circles


Download Sample Python Code - Version 2

A second version solves multiple circle packing optimization problems with the same model using multi-dimensional arrays. Python source code re-writes the optimization file and sends it to the APM server for solution. After the script executes, a figure appears that shows the configuration that was produced.


Example Solution for 10 Circles

Thanks to Frank Kampas for providing source code and animations for this challenge problem. Frank holds a Ph.D. in physics from Stanford University and can be reached at frank@physicistatlarge.com.


Record Your Best Answer