# Nonlinear Optimization and Adaptive Heuristics for Solving Irregular Object Packing Problems
## 5 Further Scalable Object Configuration Problems
### General Ellipse Packings in \(R^{2}\)  
Given a set of general ellipses \(i=1,\ \ldots,N\) in \(R^{2}\), our goal here is to find their packing into an optimized regular polygon. We will refer to this class of problems as GEP models. Specifically, for a given set of ellipses with arbitrary size and orientation, and a given integer \(M\geq 3\), our objective is to minimize the appthem (the line segment from the center of the polygon to the midpoint of one of its sides) of the regular \(M\)-polygon container. Therefore, packing ellipses into a regular polygon requires i) the determination of the maximal distance from the center of all polygon faces to each ellipse boundary (in order to contain all ellipses), and ii) the finding of the minimal distance between all pairs of the ellipses (in order to avoid ellipse overlaps as a function of ellipse center locations and orientations). The first requirement is necessary to determine the length of the polygon's appthem \(\alpha\), which is then to be minimized. The second requirement serves to prevent the ellipses from overlapping. Explicit analytical formulas for the first requirement can be directly derived. However, for the second requirement, deriving explicit analytical formulas would be complicated. Therefore, the ellipse-packing model class is based on embedding optimization calculations, using Lagrange multipliers \(\lambda\), into the overall optimization strategy. We summarize the key modeling steps below, referring to [PERSON] et al. [57] for details. Omitting index \(i\) for simpler notation, equation \(e(a,b,x^{\varepsilon},y^{\varepsilon},\theta;x,y)=0\) defines the \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & & \multicolumn{2}{c}{**LGO Result**} & \multicolumn{2}{c}{**Hybrid Result**} \\ \cline{3-5} \(R^{d}\) & \(N\) & **Objective \(r_{0}\)** & **Time (s)** & **Objective \(r_{0}\)** & **Time (s)** \\ \hline \(R^{3}\) & 10 & 19.5361 & 2.1 & 19.5361 & 23 \\  & 15 & 31.1456 & 6.6 & 31.3662 & 51.6 \\  & 20 & 44.8945 & 22.9 & 44.4319 & 172.5 \\  & 25 & 59.5338 & 73.6 & 58.7339 & 293.4 \\  & 30 & 74.9691 & 202.4 & 74.2992 & 232.9 \\  & 50 & 144.317 & 4231.9 & 142.834 & 1360 \\ \(R^{4}\) & 10 & 18.924 & 2.3 & 18.8575 & 22.9 \\  & 15 & 30.4039 & 8.2 & 30.4039 & 34.6 \\  & 20 & 41.4775 & 28.4 & 41.4858 & 74.3 \\  & 25 & 53.8574 & 95 & 53.5299 & 83.7 \\  & 30 & 66.5128 & 246.7 & 66.6449 & 102.7 \\  & 50 & 121.820 & 5056.9 & 121.806 & 552.6 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Sphere packings in \(R^{d}\) with \(d=3,4:\) illustrative results. Figure 2: A solved GSP model instance. boundary of an ellipse with semi-major and semi-minor axes \(a\) and \(b\), centered at \(\{x^{c},y^{c}\}\) and rotated counterclockwise by angle \(\theta\). The value of \(e(a,b,x^{c},y^{c},\theta;x,y)\) is negative for all points \((x,y)\) located inside the ellipse, zero for all points on the ellipse boundary, and positive for all points outside the ellipse. Here, \(\{x^{c},y^{c}\}\) and \(\theta\) are the primary decision variables for each ellipse \(i\): these variables are denoted by \(\left(x_{i}^{c},y_{i}^{c}\right)\) and \(\theta_{i}\) for \(i=1,\ \ldots,N\). All pairs of packed ellipses are prevented from overlapping by requiring that the minimum value of the ellipse equation for the first ellipse (ellipse \(i\)) for any point on the second ellipse (ellipse \(j\)) must be greater than a sufficiently small parameter \(\epsilon\geq 0\) (this way, \(e(a,b,x^{c},y^{c},\theta;x,y)\) is used to define the \(\Phi\)-function, referred to earlier, for pairs of general ellipses). This non-overlapping requirement between ellipses \(i\) and \(j\) is met utilizing the embedded Lagrange multipliers \(\lambda_{ij}\) using partial derivatives of the ellipse equation. In terms of scalability, ellipse-packing problem instances could be generated, e.g., by defining the following input structure: \(a_{i}=i^{-1/2}\), \(b_{i}=a_{i}/c\) for \(i=1,\ldots,N\), where \(c>0\) denotes the eccentricity of the ellipses.