# Nonlinear Optimization and Adaptive Heuristics for Solving Irregular Object Packing Problems
## 2 Continuous Nonlinear Optimization
### Global Optimization for Object Packings  
Notice the absence of the frequently postulated model convexity assumptions: convexity would be implied, e.g., by requiring that \(f\) and all components \(g_{j},j=1,\dots,\ m\), are convex functions, leading to essentially unimodal problems (in terms of their unique optimum value). In the absence of such convexity guarantees, instances of models (1)-(2) could have multiple local optima: consequently, we are interested in finding the globally optimal solution(s)--as opposed to finding one of the local optima. In object configuration problems, model convexity cannot be assumed: the OP model examples discussed in this work are all non-convex.  
Observe next that--by the classical extreme value theorem of [PERSON]--the postulated assumptions (\(D\) is compact, \(f\) is continuous) guarantee that the NLP model has a globally optimal solution set \(X^{*}\). Each \(x^{*}\in X^{*}\) is a globally optimal solution; \(f^{*}=f(x^{*})\) the global optimum value. The set \(X^{*}\) often--but not always--consists of a single point \(x^{*}\): we think that this is the typical scenario in irregular object-packing problems without symmetries, while models with identical objects have many equivalent global solutions.  
Generally speaking, OP problems are notoriously hard. Finding the solution set \(X^{*}\)--or finding just one global solution \(x^{*}\in X^{*}\)--of model (1)\(-\)(2) using a purely analytical solution methodology is not possible. Finding \(X^{*}\) numerically can also become very challenging, since--as a rule--the difficulty of solving larger model instances is rapidly increasing. Additional challenges arise due to the typically \"complicated\" feasible set \(D\). To illustrate the latter aspect, note that the no-overlap constraints are often nonconvex, and that their number increases quadratically as a function of the number of packed objects. Given these potentially massive difficulties, a local scope search for the best configuration is clearly insufficient on its own. A global search strategy--if carried out efficiently--leadsto high-quality feasible solutions, sometimes even to the true numerical global solution! These observations are also supported by our numerical results, based on solving various instances of hard packing problems, reviewed later in this article.  
In recent decades, global optimization (GO) has become a well-established research area: there exists a large number of books and thousands of articles that are devoted to the subject of GO. Here we only refer to the Handbook of Global Optimization volumes edited by [PERSON] and [PERSON] (1998) and [PERSON] and [PERSON] (2010). The key theoretical results regarding the most important GO model types and algorithmic solution strategies have been followed by software implementations that are used to handle a range of GO applications. Interested readers should consult, e.g., [PERSON] (2008, 2010, 2011) for discussions with extensive references to GO algorithms, software, benchmarking, and applications.  
The development and verification of robust and efficient GO software requires practically important and challenging test problems. The most widely used \"classical\" GO test problems are small-scale, either box-constrained models, or have only a handful of constraints: consult, e.g., [PERSON] et al. (2014). Hence, their numerical solution does not pose a serious challenge to state-of-the-art GO software on today's computing platforms. The scalable object-packing models discussed in this article are--or can become--useful addenda to GO test libraries.