# Nonlinear Optimization and Adaptive Heuristics for Solving Irregular Object Packing Problems
## 3 A Review of Approaches to Irregular Object Packings
### An Algorithm Framework for Object Packings  
Based on the literature reviewed and the preceding discussion, a conceptual framework for developing object-packing algorithms can be summarized as follows (obviously, implementations will be problem-specific).  
1. Create an initial feasible solution, or--more generally--a set of candidate solutions. It is possible to build candidate solutions sequentially (adding objects piecewise) or to create complete candidate solutions. Both deterministic and stochastic approaches can be used to find such initial packing configurations. The availability of feasible solutions leadsto establishing bounds related to the quality of the current best solution, which can be compared to estimates of the best possible solution (simple estimates are often easy to find). Let us point out that finding credible solution estimates can be straightforward in certain model types: notable cases are some scalable models discussed later on in this work.  
2. Using the initial feasible solution(s), solve numerically the resulting optimization model. Depending on the model type considered, solution approaches may involve global or local NLP with continuous decision variables, integer programming (IP) with discrete decision variables, or mixed variable (MILP and MINLP) models. In all these cases, finding high-quality feasible and near-optimal solutions to packing models typically requires global scope search techniques. Since it can be very hard to solve OP models to global optimality, the solution obtained is typically only an approximation of the optimal solution.  
3. In order to improve solution quality, one can apply various heuristic approaches. Such methods can be based on meta-heuristic algorithms that help find approximate solutions to complex optimization problems, with a computational effort that is deemed reasonable. Examples of heuristic methods that can be put to good use in OP are basin hopping, differential evolution, genetic algorithms, greedy randomized adaptive search, neighborhood search, simulated annealing, swarm intelligence algorithms, and tabu search. Problem-specific insight can motivate object sequencing, swapping, backtracking, and other strategies, which become part of tailored meta-heuristic algorithms. A simple but generally valid observation is that applying more insightful and sophisticated heuristics can assist in finding higher-quality solutions to hard OP problems.  
4. While executing stages 2 and 3, one can always compare the current candidate solution(s) to the estimated best solution (we will comment later on finding solution estimates). Such comparisons can be effectively used to establish algorithmic search termination criteria. Obviously, this is most useful since in OP problems with continuous decision variables the global scope search for the best solution theoretically could go on infinitely, while in discrete variable spaces, the solution effort is subject to the \"curse of dimensionality\".  
In addition to the cited OP-specific literature, we refer to three relevant volumes on heuristics: [PERSON] et al. (2019), [PERSON] (2019), and [PERSON] (2019). There are many other works devoted to this very useful (and very fashionable) topic.  
Next, we illustrate the application of various algorithmic approaches by numerically solving instances from several OP model types.