# Nonlinear Optimization and Adaptive Heuristics for Solving Irregular Object Packing Problems
## 5 Further Scalable Object Configuration Problems
### General Oval Packings in \(R^{2}\)  
Given a set of generalized ellipses (egg-shaped objects), referred to here as ovals, our goal is to find their packing into an optimized regular polygon in \(R^{2}\). We will refer to this class of problems as GOP models. As above, the objective is to minimize the area of the regular polygon that contains a given collection of ovals with arbitrary size and orientation. The extension from packing ellipses to packing ovals is not trivial. Here we provide only a brief summary, referring to [PERSON] et al. (2016) for details. The perimeter of an oval is defined by \((x/a)^{P}+e^{tx}(y/b)^{\widehat{P}}-1=0\), where \((x,y)\) denotes the location of a point on the oval perimeter, parameters \(a>0\) and \(b>0\) are the semi-major and semi-minor axes of the oval, \(p\geq 2\) is an even integer, and \(t\geq 0\) is a distortion factor. In general, an oval can be defined with arbitrary size and orientation parameters, noting that the size and distortion factors are constrained, in order to maintain the oval's convexity. The input parameters to define an optimization problem instance are the number of sides for the container and the semi-major axes, semi-minor axes, exponent, and distortion factor for each oval to be packed. The primary decision variables are the polygon's apothem and the center position and orientation of the packed ovals. There are two sets of secondary variables. The first set consists of the positions of the distance-maximizing lines pointing from each oval boundary to the center of each of the polygon faces. The second set is given by the positions of the points on one of each pair of ovals, which minimizes the value of the equation describing the other oval. These secondary variables are used to define the model constraints. Specifically, the first set of secondary variables is used to represent the constraints that keep the ovals inside the container. The second set of secondary variables is used to prevent the ovals from overlapping. These constraint sets are also generated by embedded Lagrange multiplier conditions. Omitting index \(i\) (for simpler notation), equation \(e(a,b,p,t,x^{c},y^{c},\theta;x,y)=0\) defines the perimeter of an oval centered at \(\{x^{c},y^{c}\}\) and rotated counterclockwise by angle \(\theta\). As before, together with the apothem \(\alpha\), \((x^{c},y^{c})\) and \(\theta\) are the primary decision variables for each oval. All pairs of packed ovals are prevented from overlapping by requiring that the minimum value of the oval equation for oval \(i\) for any point on oval \(j\) has to be greater than a sufficiently small parameter \(\epsilon\geq 0\). This non-overlapping requirement between ovals \(i\) and \(j\) will be met using embedded Lagrange multipliers \(\lambda_{ij}\) using partial derivatives of the oval equation. Let us point out that the slope of oval curve \(i\) equals the slope of oval curve \(j\) at the point on oval \(j\) that minimizes or maximizes the value of the function describing oval \(i\); thus, the non-overlapping constraints emerge naturally from these conditions. In terms of defining scalable models, oval packings (with their flexible parameterization options) offer tremendous potential. The table below summarizes some oval-packing test problem sets that could be used with \(M\)-polygon containers \(M\geq 3\). Note that by setting \(p=2\), \(a_{i}=b_{i}\), and \(t=0\), test case 1 becomes a general circle-packing problem for circles with radii \(a_{i}=i^{-1/2}\). With \(p=2\), \(a_{i}>b_{i}\), and \(t=0\), test case 2 becomes a general ellipse-packing problem for ellipses with semi-major and semi-minor axes, \(a_{i}=i^{-1/2}\), \(b_{i}=a_{i}/c\) with eccentricity \(c=2\). Test cases 1-6 and 8 consider ovals with the same distortion factor set (\(t=0\), 0.5, or 1). Test case 7 considers ovals with different distortion factors \(t_{i}=i/5\). To solve the model instances shown in Table 4, IPOPT linked to _Mathematica_ was used as the solver.