# Nonlinear Optimization and Adaptive Heuristics for Solving Irregular Object Packing Problems
## 5 Further Scalable Object Configuration Problems
### P-Dispersion Configurations of Oval Objects in \(R^{2}\)  
In this problem statement, we consider allocating \"sizeable\" (in other words, area-consuming) heterogeneous objects within a given feasible region in \(R^{2}\). All objects are modeled by general ovals, which cover circles and ellipses as special cases. The feasible region could be convex (modeled here by regular polygons) or non-convex (modeled here by the intersection of general ovals). Our objective is to find optimally dispersed configurations, by maximizing the minimal separation between the boundaries of the oval objects and the boundary of the feasible region instances. For brevity, we refer to this model \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Test Case** & \(\mathbf{p_{i}}\) & \(\mathbf{(a_{i}b_{i})}\) & \(\mathbf{t_{-}i}\) \\ \hline
1 & 2 & \(\left(i^{-1/2},a_{i}\right)\) & 0.0 \\
2 & 2 & \(\left(i^{-1/2},a_{i}/2\right)\) & 0.0 \\
3 & 2 & \(\left(i^{-1/2},a_{i}\right)\) & 0.5 \\
4 & 2 & \(\left(i^{-1/2},a_{i}/2\right)\) & 0.5 \\
5 & 2 & \(\left(i^{-1/2},a_{i}\right)\) & 1.0 \\
6 & 2 & \(\left(i^{-1/2},a_{i}/2\right)\) & 1.0 \\
7 & 2 & \(\left(i^{-1/2},a_{i}\right)\) & \(i/5\) \\
8 & 4 & \(\left(i^{-1/2},a_{i}\right)\) & 0.0 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Illustrative GOP model instances. Figure 4: A solved GOP model instance. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Container Sides** & **n** & **Objective \(\mathbf{\alpha}\)** & **Container Area** & **Time (s)** \\ \hline \(M=5\) & 5 & 2.2389 & 11.9184 & 127.4 \\  & 6 & 2.2976 & 12.5509 & 189.9 \\  & 7 & 2.3291 & 12.898 & 299.6 \\  & 8 & 2.3904 & 13.5858 & 312.7 \\  & 9 & 2.5637 & 15.6268 & 753.6 \\  & 10 & 2.7022 & 17.3613 & 757.5 \\ \hline \(M=10\) & 5 & 2.0385 & 12.2126 & 210.2 \\  & 6 & 2.0892 & 12.8277 & 351.3 \\  & 7 & 2.1804 & 13.9716 & 437 \\  & 8 & 2.3291 & 15.9423 & 539 \\  & 9 & 2.3294 & 15.9465 & 888.4 \\  & 10 & 2.4129 & 17.1113 & 1493 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Illustrative GOP model results. class as PDO (p-dispersion _with_ ovals). Here we provide a summary of our modeling and solution approach, referring to [PERSON] et al. (2018) for further details. In ([PERSON] et al., 2018), embedded Lagrange multiplier conditions have been used to produce optimized oval configurations with the objective of minimizing the area of the feasible region that contains a given collection of oval objects since our goal was to produce dense object configurations. Now, using a similar Lagrangian framework, our aim is to produce optimally dispersed configurations by maximizing the separation between the boundaries of the oval objects and the boundary of the feasible region. A pair of oval objects is maximally dispersed by maximizing the minimum value of the oval equation for object \(i\) for any point on the oval equation for object \(j\), achieved by using embedded \(\lambda_{ji}\) Lagrange multiplier conditions. We note that in the dispersion case considered here, the Lagrange multipliers \(\lambda_{ji}\) must be negative to obtain the minimum: this requirement. with respect to the sign of \(\lambda_{ji}\), is enforced by appropriately setting variable bounds during the optimization. In the numerical examples presented here, a heuristic global optimization strategy (based on selecting multiple starting points) is used: we use these randomized initial solutions followed by calls to the local solver IPOPT linked to _Mathematica_. Three key parameters guide our optimization strategy: the number of random starts, the solver seed, and the maximum number of solver iterations (for clarity, these are not IPOPT internal iterations; the maximum number of solver iterations takes the final result of one solver iteration and uses it as the input for the next solver iteration).