Non-Uniform Size Circle Packings

Introductory Notes

Point arrangements and closely related uniform circle packings within given bodies (the latter most typically being n-dimensional intervals and circles for ) have been intensively studied by the mathematical community for several decades. Such models are not only of pure academic interest, but are also closely related to important problems in numerical mathematics (integration, experimental design), physics and chemistry (potential models, crystal and molecule structures), and biology (viral morphology), just to name a few application areas.

There is a considerable body of literature devoted to these subjects [51-59]. Several of these works provide extensive lists of further references.

The applicability of global optimization tools to analyze and solve instances of various point arrangement (potential) models has been demonstrated [60-62]. We emphasize here that the issue of non-uniform size circle (or more general object) packings is entirely outside of the scope of "traditional" (purely analytical) studies, while GO can still be applied to such, as well as to many other, model variants and extensions.

For illustration, in this section we use global optimization to pack different-size circles into the smallest possible circle. Since this model formulation typically has infinitely many solutions per se, we will additionally try to bring the circles as close together as possible. The primary objective is to find the embedding circle with the smallest radius; the secondary objective--bringing the circles close together--is added as a second criterion function. A linear combination of the two objectives is used in an aggregate objective function.

Note that alternative formulations are also possible and that rotational symmetries of solutions can also be avoided by added constraints, thereby making the solution of a specific model formulation essentially unique.

Model Formulation and Numerical Examples Using NMinimize, MathOptimizer, and MathOptimizer Professional

The solution is demonstrated using three different optimizers: NMinimize, MathOptimizer, and MathOptimizer Professional. MathOptimizer Professional is a recently introduced product [39] in which the actual optimization is performed by an external executable--the Lipschitz Global Optimizer (LGO) solver engine--on a Windows dynamic link library (dll) model function. The latter is automatically generated from a model formulated in Mathematica.

Without going into details, which are outside of the scope of this article, we should mention that LGO is a global/local solver suite that has been discussed, for example, in [35-37]. The LGO engine can also be used to handle models set up in Excel [63] and GAMS [64], in addition to its C or Fortran compiler-based implementations. Let us note that [65] presents a detailed and fully reproducible comparative assessment of LGO versus several state-of-art local nonlinear solvers: this comparison is based on solving an extensive set of GAMS models, and it was done by the GAMS Development Corporation (thus it can be considered as reasonably objective). These tests demonstrate that in a significant percentage of nonlinear optimization (GAMS) models, global scope search is necessary indeed; furthermore, that LGO compares favorably to the solvers considered (CONOPT, MINOS, and SNOPT).

In the following model equations, the center of circle i is denoted by {x[i],y[i]} and the radius of circle i is r[i]. The distance from the origin to the most distant point in a circle is given by the radius of the circle plus the distance of the center of the circle from the origin. For circle i, this distance is given by dd[i], as formulated here.

The distance between the centers of the circles i and j is given by p[i,j]. Two circles do not overlap, if the sum of their radii minus the distance between their centers is not greater than 0: the corresponding term is given by dd[i,j] for circles i and j.

The optimization variables for describing the position of n circles are the coordinates of the centers of the circles.

The first objective, defined by obj1, is to minimize the radius of a circle circumscribing the packed circles, which is the maximum of the values dd[i] for the n circles. MathOptimizer Professional only evaluates Max for two arguments, requiring the use of a table of constraints to define the first objective.

The second objective, defined by obj2, is to minimize the average distance between the centers of the n circles.

The overall objective function is defined now as the weighted average of the two objective functions obj1 and obj2, with being the weight parameter. Note that the second objective function component is normalized to be the average distance between the centers of the circles, so that the two objective functions will remain of comparable magnitude. For , the objective function is aimed at finding the smallest embedding circle. For , the objective function expresses solely the average distance between the circle centers, providing the "tightest possible" packing.

The requirement that the packed circles not overlap means that dd[i,j]≤0 for all pairs of i and j. The input form differs somewhat for the different optimizers. For MathOptimizer Professional, it is necessary to add the constraints that define rmax.

The problem as formulated has considerable symmetry. To reduce the symmetry, several constraints are added (to set the first circle object position and the relative location of the second and third circle objects), so that the results of the different optimizers can be more easily compared. Note that adding further similar constraints could increase the overall model complexity significantly, and thus it is avoided.

MathOptimizer and MathOptimizer Professional require bounds on the variables, which are expressed somewhat differently. Since the formulation for MathOptimizer Professional requires an extra variable, the variables with bounds are constructed in one function.

The function in[i] produces a constraint describing circle i for use in the InequalityPlot function.

The results of the calculations are shown as the combination of three plots: p1 uses InequalityPlot to show the circles with a table of inequalities defining the circles; p2 is a plot of the circumscribing circle; p3 is a plot of the centers of the circles. show combines the plots.

Having defined the variables, objective function, and constraints, we now define functions for performing the circle packing and displaying the results using MathOptimizer, MathOptimizer Professional, and NMinimize. The numerical outputs of the following three functions are the values of the two objective functions and the complete solution.

In our illustrative examples included here, five circles generated with radii 0.2 to 1.0 are used, together with a value of 0.5, as the key problem input.

Numerical Example Using MathOptimizer Professional

AbsoluteTiming is used in this example since Timing will not include the time required by the compiler and the LGO executable.

Comparison of the MathOptimizer and MathOptimizer Professional results shows that they are very similar. The MathOptimizer Professional result has somewhat lower values for both objective functions, and it also leads to smaller constraint violations: the maximal overlap of the circles equals approximately . The calculation time for MathOptimizer Professional is approximately 30 times smaller, due its use of a compiled executable for minimization and a compiled dll for objective function and constraint evaluation. In further numerical tests, we have used MathOptimizer Professional to solve similar models up to circles, without any other prior circle object arrangement specifications: these results are reported elsewhere [66].

Numerical Example Using NMinimize

Next, we also completed a few experimental runs to see how NMinimize performs on the same circle packing test problems. The circle packing obtained was not as good as in the result produced by MathOptimizer (or by MathOptimizer Professional).

Note that we also did further extensive tests with respect to all three solvers. The corresponding--far more detailed--numerical results will be reported and discussed elsewhere, for example, in our forthcoming book [29].