In this work, we present model development and numerical solution approaches to the general problem of packing a collection of ellipses into an optimized regular polygon. Our modeling and solution strategy is based on the concept of embedded Lagrange multipliers. This concept is applicable to a wide range of optimization problems in which explicit analytical expressions for the objective function and/or constraints are not available. Within this Lagrangian setting, we aim at minimizing the apothem of the regular polygon while preventing ellipse overlaps: our solution strategy proceeds towards meeting these two objectives simultaneously. To solve the ellipse packing models, we use the LGO solver system for global-local nonlinear optimization; for larger model instances, we use a “naïve” combination of pure random start and local search. The numerical results presented demonstrate the applicability of our modeling and optimization approach to a broad class of difficult, highly non-convex ellipse packing problems, by consistently providing high quality feasible solutions in all model instances considered.
Research Report, January 2018. Submitted for publication.