# Nonlinear Optimization and Adaptive Heuristics for Solving Irregular Object Packing Problems
## 3 A Review of Approaches to Irregular Object Packings  
### Algorithmic and Heuristic Approaches  
We discuss these approaches together, since they are often utilized in problem-type dependent combinations. [PERSON] and [PERSON] (2008) offer an early survey on the application of Operational Research techniques to the solution of packing problems. Their survey is focused on the modeling and solution of practically motivated problems in two and three dimensions: both exact and heuristic solution approaches are reviewed. They point out the well-known fact that even the \"simple\" rectangular packing problem class is known to be \"hard\" (in technical terms, NP-complete). Therefore, it is often impossible to provide exact solutions for sizeable problems within a reasonable computational time. Two-dimensional rectangular packing, pallet loading, one- and two-dimensional bin packing, strip packing, and three-dimensional container-packing problems are discussed, with references. For handling the more difficult problem types, common sense-based insights and heuristic approaches are also utilized. In the case of packing non-rectangular objects, the approaches vary according to their geometry. The authors also note the potential of stochastic modeling and randomized solution approaches: an observation that remains valid for the case of handling irregular packings. Let us emphasize that irregular packings typically lead to even far more difficult problem types than the rectangular packings discussed by the authors. [PERSON] and [PERSON] (2008) present a tutorial with the goal of covering the core geometric approaches and methods employed by researchers in the cutting and packing of irregular shapes. They note the need for geometric tools to handle the wide variety and complexity of shapes that need to be packed. The paper describes the operations of several different approaches for dealing with the geometry required in the solution of packing problems. The methods discussed include raster methods (which divide the continuous stock sheet into discrete areas), trigonometric analysis (of packed polygons), no-fit polygons (used to check whether two polygons overlap or not), and \(\Phi\)-functions (used to represent all mutual positions of two objects, to decide whether they overlap or not). Let us add here that [PERSON] et al. (2010) provide a review of some earlier studies that use \(\Phi\)-functions, more recent applications will be referred to in this work. [PERSON] and [PERSON] (2010) discuss irregular shape nesting (packing) problems. They emphasize the essential need for utilizing heuristic approaches. They also propose dividing the approaches into methods that work with partial solutions, building these up to a final design (constructive heuristics), and methods that work with complete proposed solutions where changes are made in order to find improvements (improvement heuristics). The order in which the pieces are selected for inclusion in a constructive heuristic can be based on fixed rules, dynamic selection, and randomization, with or without backtracking options. These choices can have a significant influence on the resulting (proposed) solution. Working with complete solutions requires the design and application of some efficient local search heuristics, which depend on the problem representation. The problem can be considered in its entirety (physical layout), or as a sequence of the objects to pack to arrive at the final layout. Moves can be based on swapping objects and inserting objects. The authors summarize their findings in an insightful diagram (cf. [7], Figure 18), which displays a proposed organization of nesting solution approaches. [PERSON] [12] presents and discusses research carried out in support of the cargo accommodation of space vehicles. The typical goal of such studies is to maximize the loaded cargo, while also considering additional requirements. The packed items can often be modeled as parallelepipeds, but this approximation is frequently not acceptable.