# Nesting Process Automation in the Footwear Industry: A Hybrid Approach to Minimize Material Waste
## 2 State of the Art
Additionally, the work by [PERSON] and [PERSON] [10] proposes integer linear programming models (programming problems where some or all of the variables are restricted to be integers), while [PERSON] and [PERSON] [11] present an exact solution for the two-dimensional knapsack problem where the pieces are rectangular. This is one of the few examples of exact algorithms developed to address a subproblem within nesting, specifically the placement of small pieces in gaps left by larger ones. The previous study could only optimally prove a solution on two out of the three examples of broken crystals (up to 10 parts), concluding that the algorithm is unlikely to be viable for optimally solving nesting instances of manageable size. Consequently, it is recommended for use primarily in filling smaller cutouts and holes with the smallest pieces. Heuristic solutions to the nesting problem can be approached either by generating partial solutions or by working directly toward global solutions. Various heuristic strategies have been applied to address the nesting problem, with the following being the most notable:  
* The Bottom-Left strategy, first proposed by [PERSON] and [PERSON] [6], arranges parts by placing each one \"as low and as far to the left as possible\". * The TOPOS algorithm [12] employs a strategy that iteratively builds a partial solution by adding the part that best satisfies the algorithm's selected criteria from those proposed by it. Newly added parts are positioned around the already-placed set. An exhaustive analysis of algorithm performance is conducted, testing a combination of 126 possibilities, among the criteria proposed, and comparing these results with those obtained with other algorithms using a dataset common in the literature. * The JOSTLE algorithm by [PERSON] et al. [3] introduces the possibility of placing parts behind those already positioned. This involves a series of iterations of a simple placement of parts, consecutively to the left and then to the right, resembling the effect of'shaking' a box, the parts thus being rearranged in their best position. Conversely, numerous publications propose solutions based on the linear programming (LP) technique for finding the best possible solution with an objective and a set of restrictions for the compaction and part separation techniques, often combined with various heuristic algorithms to achieve an improved initial solution. The compaction technique can improve a valid initial nesting by applying a series of coordinated movements of the pieces to obtain an optimal arrangement. During these movements, no overlapping between parts is allowed and they must be continuous, so that parts cannot jump over each other. Furthermore, rotations are not allowed. The technique is repeated iteratively as long as improved nesting is obtained, with less than ten iterations usually being necessary to completely compact a design. The separation technique focuses on resolving overlapping of parts in initial arrangements. As in compaction, it consists of applying coordinated movements to the parts. This technique is also iterative, and in most cases, fewer than ten iterations are required to fully eliminate overlaps. In the application of metaheuristic algorithms for solving the nesting problem, several notable studies are as follows:  
* Genetic algorithm (GA): This algorithm has been employed by researchers such as [PERSON] et al. [13] and [PERSON] and [PERSON] [14], among others. Recently, [PERSON] et al. [15] combined a genetic algorithm (the problem-solving technique that was inspired by biological evolution as a strategy for the resolution) with a greedy strategy to address the nesting of irregular parts on a rectangular master surface. Their approach includes a coding technique that significantly reduces the computations of the algorithm. * Particle swarm algorithm (PSO): Developed by [PERSON] and [PERSON] [16], this algorithm is based on the collective movement of living organisms.