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.
A simple example is
augLag[{x + y, x^2 + y^2 <= 1, x/3 + 2 y/3 == 1/2}, {{x, -1}, {y, 1}}]
{0.568338, {x -> -0.363325, y -> 0.931662}, {\[Lambda][[1]] -> 0.301511, \[Lambda][[2]] -> -2.34272},
"Max Cons Viol" -> 1.63459*10^-8}
For interpreting the Lagrange multiplier values, note that >= constraints are converted to <= constraints. Also, only nonzero multiplier values are returned.
Comments and suggestions are welcome.
Attachments:
