# Algorithmic Advances for 1.5-Dimensional Two-Stage Cutting Stock Problem
## 2 Comprehensive Technical Review of Relevant Literature
Their approach utilizes a Row-and-Column generation framework to solve the linear programming relaxation, involving a knapsack subproblem and a nonlinear integer programming subproblem for which they develop a decomposition-based exact solution method with pseudo-polynomial time complexity. In [19], the Generate-and-Solve (G&S) framework is implemented for the 1D-CSP, employing a recursive pattern generation procedure structured as a search tree. This tree represents all feasible cutting patterns, where the root node corresponds to the length of the large object, the internal nodes represent the inclusion of specific item types, and the leaf nodes indicate the cut loss. By limiting the tree's height to the number of different item types and constraining the number of items per type to their respective demands, the method efficiently generates a reduced set of promising patterns. The G&S framework then utilizes an exact solver on these reduced instances, consistently obtaining quasi-optimal solutions across various instance sizes. This approach effectively balances computational efficiency and solution quality, and when integrated with Column Generation techniques, it has the potential to enhance convergence in branch-and-price algorithms, especially when Column Generation alone does not yield high-quality integer solutions. Recent advancements in cutting and packing optimization encompass a diverse range of settings and methodologies. For instance, ref. [20] presents a linear programming model designed to minimize trim loss in a Make-to-Order paper mill. This model stands out from previous studies by incorporating flexible master reel widths and reusing stocked over-produced and leftover reels to fulfill customer orders. The model explicitly considers operational and technological constraints and employs a post-optimization procedure to ensure integer-feasible solutions with minimal computational effort. Both [21; 22] employ iterative strategies based on Column-and-Constraint Generation (C&CG) frameworks to address distinct problems. The approach in [21] is nested and addresses non-convex, bi-level subproblems under complex uncertainties for solving the Two-Stage Robust Optimization model for prosumers considering multiple uncertainties. In contrast, the [22] implementation is more conventional, focusing on container booking decisions with uncertain demands and emphasizing computational efficiency and heuristic initialization. Despite sharing the common objective of iteratively refining the solution space, these techniques fundamentally differ in the complexity of the subproblems and the nature of the constraints introduced at each iteration. Ref. [23] develops a robust optimization model for a Two-Dimensional Strip-Packing Problem characterized by uncertain demands and the availability of multiple strip sizes, employing KKT-based transformations integrated with column generation. Ref. [24] concentrates on rebar cutting operations in reinforced concrete beams, proposing a Two-Stage optimization algorithm to minimize cutting waste and rebar usage. Furthermore, a recent Deep Reinforcement Learning (DRL)-based algorithm proposed by [25] addresses large-scale One-Dimensional Constraint Satisfaction Problems (CSPs) by learning cutting patterns directly from data, achieving high material utilization. Although also addressing a Cutting Stock-type problem, their method is more narrowly tailored to specific industrial constraints and employs heuristic strategies rather than the more general, exact methods prevalent in the literature. These studies underscore the diversity of approaches employed in various cutting and packing environments. While all provide valuable insights, the problem addressed in this paper presents its own unique challenges that necessitate a meticulous adaptation of state-of-the-art methods. In summary, while numerous studies concentrate on reducing the number of patterns utilized in multi-stage CSPs, this research pursues the objective of minimizing the total trim loss throughout all stages.