Packing Circles in a Square of Minimum Size
Introduction
This application optimizes and visualizes the packing of circles (of varying radii) in a square, such that the side-length of the square is minimized.
One solution for 20 circles (with a radius of 1 to 20) is visualized below
This is a difficult global optimization problem and demands strong solvers. This application uses Maple's Global Optimization Toolbox.
Circle packing (and packing optimization in general) is characterized by a large optimization space and many constraints; for this application, 20 circles generates 230 constraint equations.
The number of circles can be increased to create an increasingly complex problem; Maple automatically generates the symbolic constrain equations.
Applications like this are used to stress-test global optimizers.
Setup
Number of circles
Radius of circle i is equal to i
Decision Variables and Optimization Bounds
The decision variables are the coordinates () of the centers of the circles, and the side length len of the circumscribing square.
Constraints
is the maximum distance from the origin to a point on the circumference of circle i
is the distance between the centers of any two circles minus their radii
The side-length of the square len must be greater than or equal to , for all circles. That is, the maximum distance between the furthest point on a circle's circumference and the origin must be smaller than the side length of the square (assuming the square is positioned on the origin)
For circles i and j not to overlap, must be zero or greater for all pairs of circles:
Hence the entire set of constraints
Optimization and Results