# Algorithmic Advances for 1.5-Dimensional Two-Stage Cutting Stock Problem
## 2 Comprehensive Technical Review of Relevant Literature  
A substantial body of literature exists on Cutting Stock Problems (CSPs), encompassing both 1D and 2D scenarios with constrained cutting patterns and diverse objective functions. The following references provide insightful perspectives on the field. The linear programming approach proposed by [5,6] for one-object and one-stage CSPs is based on column generation, where the pricing problem is solved using dynamic programming. Ref. [7] developed a combined column generation and branch-and-bound algorithm to obtain optimal integer solutions for binary CSPs. Ref. [8] presents a nested decomposition approach for solving a three-stage two-dimensional (2D) CSP with orthogonal guillotine cuts. This method, aimed at minimizing waste and accommodating various industrial constraints, employs a recursive column generation algorithm that provides lower bounds and feasible upper bounds, facilitating potential integration into branch-and-bound for optimal solutions. Ref. [9] solves the 1.5-D assortment problem with multiple objectives using a genetic algorithm, generating cutting patterns with implicit enumeration. Ref. [10] developed an accelerated column generation method by introducing dual-optimal inequalities, reducing the number of column generation iterations and run time. In [11], polylithic solution approaches integrated into an ERP system are developed to address real-world 1D and 2D cutting stock problems in the paper industry, incorporating novel column generation techniques for handling multiple master roll widths, limited stock availability, and underproduction minimization. The enhanced heuristic algorithm in [12]addresses 2D CSPs with constrained and guillotine cutting and multiple stock objects. It is based on a multi-phase genetic algorithm, where the objective function is not the residual area but a modified trim loss equation. Despite this, the most flexible approach in the literature is that proposed by [13; 14], who developed a linear programming model based on the generation of columns for the multi-stage problem. The presence of multiple stages presents the challenge of generating intermediate objects. This challenge has been addressed through a revised separation problem for generating the rows of the constraint matrix, where the rows correspond to the items. However, their focus is typically on minimizing the number of patterns used in the first stage rather than the total trim loss. Refs. [15; 16] classify the 1D TSCSP as a Column-Dependent Row (CDR) problem with no interactions. This class of problems is characterized by the presence of so-called linking constraints, which, in the context of CSPs, are associated with the rows corresponding to intermediate orders. These constraints are contained within the connecting matrices of the main constraint matrix. They outlined a simultaneous Row-and-Column generation algorithm based on three assumptions, which correctly price columns in the absence of certain linking constraints and allow for the generation of multiple intermediate orders at a time. In [17], they developed a hybrid algorithm based on a branch-and-price approach, applying a second-level column generation to the row-generating subproblem for the unknown intermediate orders. Importantly, their objective is also to minimize the number of first-stage patterns used, rather than minimizing the total trim loss. Additionally, they made a comparison with [PERSON]'s approach, highlighting the differences in terms of the computational time and solution gap. Ref. [18] tackles a new variant of the Cutting Stock Problem involving two-dimensional skiving and significant setup costs. They consider scenarios where the output sheets are longer but narrower than the input coils, allowing the combination of two or more coils to satisfy the sheet demands. To minimize both material and setup costs, they propose an integer programming formulation characterized by an exponential number of binary variables and column-dependent constraints.