Optimization Online


Optimized Ellipse Packings in Regular Polygons Using Embedded Lagrange Multipliers

Frank J. Kampas (frank***at***physicistatlarge.com)
Ignacio Castillo (icastillo***at***wlu.ca)
Janos D. Pinter (Janos.D.Pinter***at***gmail.com)

Abstract: 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 nave 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.

Keywords: General Ellipse Packings in Polygons; Model Development Using Embedded Lagrange Multipliers; Global and Local Nonlinear Optimization; LGO Solver Suite; Numerical Results

Category 1: Global Optimization

Category 2: Optimization Software and Modeling Systems

Category 3: Global Optimization (Applications )

Citation: Research Report, January 2018. Submitted for publication.

Download: [PDF]

Entry Submitted: 02/22/2016
Entry Accepted: 03/01/2016
Entry Last Modified: 01/14/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society