Optimized ellipse packings in regular polygons

We present model development and numerical solution approaches to the problem of packing a general set of ellipses without overlaps into an optimized polygon. Specifically, for a given set of ellipses, and a chosen integer m ≥ 3, we minimize the apothem of the regular m-polygon container. Our modeling and solution strategy is based on the concept of embedded Lagrange multipliers. To solve models with up to n ≤ 10 ellipses, we use the LGO solver suite for global–local nonlinear optimization. In order to reduce increasing runtimes, for model instances with 10 ≤ n ≤ 20 ellipses, we apply local search launching the Ipopt solver from selected random starting points. The numerical results demonstrate the applicability of our modeling and optimization approach to a broad class of highly non-convex ellipse packing problems, by consistently returning good quality feasible solutions in all (231) illustrative model instances considered here.