# A Petri Net-Based Algorithm for Solving the One-Dimensional Cutting Stock Problem
## 2 Literature Review  
It is widely considered that [PERSON] first addressed the 1D-CSP in [14] providing an LP formulation of the problem and using the multipliers method to solve it. Later, refs. [15; 16] used the column generation technique to solve the integer linear programming formulation by addressing an associated knapsack problem. Following the introduction of the column generation technique, several procedures were developed to improve its computational performance using branch-and-price algorithms [17; 18; 19; 20]. Other algorithms have focused on constructing and reducing the number of patterns [21; 22; 23; 24; 25]. Alternative approaches to modeling and solving the 1D-CSP include the arc-flow and one-cut formulations. The arc-flow formulation, a graph-based approach, was introduced in [26]. Recently, [27] proposed and compared arc-flow formulations based on other algorithms. One-cut formulations have received little attention since their use in [28]. Moreover, [29] proved the equivalence among pattern-based formulations, such as that of Gilmore & Gomory [15; 16], and the arc-flow and one-cut formulations. [30] used dynamic programming to solve the 1D-CSP, and [31] showed the relationship between arc-flow formulations and dynamic programming in solving optimization problems. Additionally, a comprehensive survey of LP methods used to solve the 1D-CSP up to 2015 can be found in [32]. LP methods are restricted to instances of a small number of items, and to overcome this limitation, many researchers have proposed metaheuristic methods like genetic algorithms. However, the use of genetic algorithms faces the difficulty of finding the best way to encode the solutions or cutting patterns, as pointed out in [33; 34; 35; 36]. Evolutionary programming was used in [7; 37] to address the 1D-CSP with and without contiguity. Additionally, ref. [38] concluded that evolutionary programming performs better than genetic algorithms for solving the 1D-CSP. Swarm intelligence algorithms, such as particle swarm optimization algorithms [39; 40; 41; 42] and ant colony optimization algorithms [43; 44; 45], have also been used to solve the 1D-CSP. The main issues with these two algorithms are parameter tuning and the need for hybridizations to avoid premature convergence and control the search space. Additionally, discretization procedures are required since these algorithms are better suited for continuous problems. Other metaheuristic algorithms for solving the 1D-CSP include tabu search, simulated annealing [46], and iterative local search [47; 48]. More recently, ref. [49] introduced the least-lost algorithm to simultaneously minimize waste and stocks with waste in the 1D-CSP, showing better results than the evolutionary programming algorithm of [7]. Ref. [50] compares a Generate and Solve algorithm to the column generation technique. The Generate and Solve algorithm uses a reduction technique based on the one presented in [51] to deal with large instances of the 1D-CSP. Although the algorithm is not better than the column generation technique, it can solve larger instances in acceptable computational time with quasi-optimal solutions. Ref. [52] introduces a deep reinforcement learning algorithm to minimize the number of stocks and maximize the length of leftovers. The algorithm performs well in terms of computational time and handling large instances. The algorithm we propose in this paper covers some of the limitations of the methods described above. Unlike LP methods, our algorithm is capable of addressing large instances as shown in Sections 6 and 7 in acceptable computational time. It only needs the instance information to construct the PN model and the tuning of two parameters for the filtered beam search algorithm, while most metaheuristic algorithms and hybridizations require more parameters to address large instances of the 1D-CSP.