# Nonlinear Optimization and Adaptive Heuristics for Solving Irregular Object Packing Problems
## 4 General Circle Packings
### Solving GCP Instances: Illustrative Results  
Optimization model development environments can be used to efficiently formulate and solve scalable object configuration problems. Scalable models require only some input parameter changes (in GCP, the number of circles to pack and their sizes), in order to create new instances. Typically, a range of global and local NLP solver engines are linked to the leading optimization model development environments. This allows flexible solver option changes and directly supports the comparative assessment of solver capabilities for a given set of models. In our OP studies discussed here, we have been using the optimization model development environment AMPL [48] and the scientific-technical computing system _Mathematica_[49] with several available solver options.  
The GCP model class is the simplest among the scalable OP models considered here. However, it already poses a numerical challenge to solvers--even for the smallest model instances. The results presented below illustrate this point, based on using six solver options (CONOPT, IPOPT, LGO, LOQO, MINOS, and SNOPT) linked to AMPL.  
Let us note here that the solver LGO is capable of determining high-quality numerical solutions to global optimization problems that have (possibly many) locally optimal solutions: for theoretical background and implementation details, consult [50; 51; 52; 53]. The other solvers CONOPT, IPOPT, LOQO, MINOS, and SNOPT are widely used local optimization solvers: for summary information, consult, e.g., the AMPL website [48].  
Table 1 includes the best-known results retrieved from [3], for instances of the GCP model class with \(r_{i}=i\), for \(i=1,\ldots,N\), \(N=5,\ldots,\) 10. The rate of deviation of the solver solution \(f^{s}\) from the best-known solution \(f^{s}\) is defined as \(\frac{f^{s}}{f^{s}}\): for high-precision solutions, this rate is close to 1, while larger values indicate less precise numerical solutions.  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**No. of Circles** & **5** & **6** & **7** & **8** & **9** & **10** \\ \hline Best known & 9.001397746 & 11.05704040 & 13.46211068 & 16.22174668 & 19.23319391 & 22.00019301 \\ \hline conopt & 9.001397746 & 11.27687246 & 13.69914165 & 16.89847646 & 19.55248862 & 24.2784228 \\ iopt & 9.001397671 & 11.53266465 & 13.69194153 & 16.63722613 & 20.15497158 & 23.37559224 \\ lgo & 9.001397749 & 11.05704040 & 13.69914165 & 16.22174668 & 19.76606329 & 22.55237926 \\ loq & 9.001397757 & 11.53266476 & 13.69914168 & 16.63722632 & 20.15497177 & 23.38725283 \\ minos & 9.001397746 & 11.53266474 & 13.69914165 & 16.44050689 & 20.27681461 & 23.42606205 \\ snopt & 9.001397746 & 11.53266474 & 13.69913854 & 16.63722700 & 20.15497175 & 23.42606205 \\ \hline \hline \end{tabularAs these results indicate, all solvers easily handle the smallest GCP model instance included here, but thereafter, all the local solvers fail to find the best solution. LGO, a global scope solver--used here without any added heuristics--fares better than the local solvers: in default usage mode, LGO finds the global solution in three out of six cases, but it misses the global solution by 1.8% to 2.8% in the other three cases.  
Table 1 merely serves to illustrate the optimization challenge implied by the proposed model class, noting again that GCP is the simplest model class discussed here. The runtimes for the local solvers--including LGO when used in local solver mode--for each of these small-scale problems are just a fraction of a second. The LGO runtime--when used in global solver mode--is 12.53 s for the largest model (with \(N=10\)) included above.  
To visualize the numerical solution of a GCP model, see Figure 1 below, which corresponds to the 10-circle model instance from the Zimmermann GCP challenge. To handle GCP models, we also used LGO linked _to Mathematica_ with the product name _MathOptimizer Professional_[53]. All visual illustrations in this article were produced using _Mathematica_.