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.
Citation
Research Report, January 2018. Submitted for publication.
Article
View Optimized Ellipse Packings in Regular Polygons Using Embedded Lagrange Multipliers