# Nesting Process Automation in the Footwear Industry: A Hybrid Approach to Minimize Material Waste
## 2 State of the Art  
Cutting and packing problems are classified as NP-hard. NP problems are hard-to-solve decision problems studied by computational complexity theory. Within this framework, NP-hard problems are at least as challenging as NP problems. The two-dimensional rectangular nesting problem has been proven to be NP-complete [1]. Due to the added complexity of handling irregular parts, nesting problems are also considered NP-complete. Furthermore, the nesting problem encompasses considerable variability, with definitions that depend on the type of parts, containers, constraints, etc. In studies where the master surface is typically a rectangle or an infinite strip, several common features are often overlooked:  
* Convexity of the parts is frequently avoided. * Free rotations are generally restricted, with only some specific rotation of the parts allowed in certain algorithms. * Most solutions have been validated for both regular and irregular shapes or parts, on rectangular base surfaces, whether finite on both sides or infinite on one side. Nesting has even been studied on irregular base surfaces, such as leather in the footwear or fashion industries. However, no studies to date specifically address leather nesting for moccasin shoe parts or Strobel parts, marking this as a novel research area. Moccasin is a type of footwear in which a single piece of leather envelopes the entire foot. Strobel is another type of footwear, which takes its name from the method used to sew together the two pieces that conform it: the sole or lower part of the foot and the body, which covers the rest. Moccasins and Strobel shoes are unique in that they each incorporate either a single piece, or two or three smaller parts. During nesting, gaps of unused material typically appear between parts, which can accommodate smaller ones. However, the limited number of those parts in these types of shoes increases waste and complicates space optimization. Most research articles focus on solutions for rolls of material with a fixed width and infinite length [2; 3]. In this type of positioning, parts must be arranged to minimize both the area of material and the length of the roll used. This problem is commonly known in the literature as strip packing and is one of the most widely applied techniques for cutting parts on synthetic material. One of the earliest algorithms proposed for strip packing was developed by [PERSON] [4], which introduced the concept of No-Fit-Polygon (NFP) to reduce the computational costs of intersections between two parts--a technique that remains in widespread use. In fact, among the different geometric tools developed to deal with nesting, the current mainstream method is NFP, as stated in [5]. [PERSON] and [PERSON] [6] later presented highly influential algorithms for nesting problems, employing a tree-search-based method in [PERSON]'s previous work with [PERSON] [7; 8] and on the NFP concept. Tree searches are tree-type data structures used for search optimization, where efficiency is one of their main characteristics. Most solutions proposed to minimize the space occupied in the placement of rely on heuristic algorithms (search for solutions that are not perfect, but good enough), as no exact algorithms have yet been developed. Only one approach in the literature, [9], proposes a mixed programming model (MIP) for parts with fixed orientation to solve the compaction and separation problem. This heuristic algorithm builds on the NFP concept and defines the inner-fit-rectangle approach, applying the same calculation rules as the NFP but on the inner side, thereby accelerating intersection calculations with the external edges. Following this, the Bottom-Left Greedy heuristic procedure is applied [2], introducing a random weighted length criterion that selects the longest parts with priority.