Packing problems have O(n^2) inequality constraints for packing n objects, which can make them computationally challenging. The attached notebook contains an experimental augmented Lagrangian nonlinear minimizer which uses FindMinimum for minimizing the unconstrained augmented Lagrangian. Results are shown for packing 10, 20, 30, and 40 integer radii circles in a circle from random starting locations. The code is approximately 10 times faster than FindMinimum’s Interior Point solver for packing 10 circles and approximately 30 times faster for packing 20 circles. The function call is the same as FindMinimum.
For interpreting the Lagrange multiplier values, note that >= constraints are converted to <= constraints. Also, only nonzero multiplier values are returned.
I mean the 10 circle solution (above) looks like the minimal radius found could yet decrease if only the yellow marked circles moved towards the center and the two small circles near the center moved outward to the boundary somewhere between bigger ones?
Have you tried the algorithm with a set of sample circles known to fit into a circumventing circle, like
I did not expect the results to be global optima, since I was starting each calculation from only one randomly chosen set of initial values. What I wanted to do was to compare the interior point method used by FindMinimum with the augmented Lagrangian method I had coded, for a problem with many more constraints than variables.
Just for fun, what is the outcome of MathOptimizer Professional if one circle has radius 1 and the other nine circles have radius 0.52? Thanks in advance!
