# Algorithmic Advances for 1.5-Dimensional Two-Stage Cutting Stock Problem
## 4 Solution Approach
### Row-and-Column Generation Algorithm  
There is a rich body of literature available on Cutting Stock Problems, dealing with both one-dimensional and two-dimensional cases, where Column Generation is employed. It starts with the Relaxed and Restricted Master Problem (RRMP), where each diagonal block is initialized with a small subset of cutting patterns and the decision variables are real values. The idea is to generate the least number of patterns necessary for the optimal solution. This approach is based on the iterative resolution of the Relaxed and Restricted Master Problem (RRMP) and an auxiliary model called the Pricing Subproblem (PSP), which has the form of a knapsack problem. The first dynamic approach for classic CSP was proposed by [5; 6] and can be extended to the case of two stages when the intermediate stock rolls are already known. In that case, a Column Generation algorithm that comprises two auxiliary models, each related to a specific cutting stage, is sufficient. If intermediate rolls are unknown in advance, a more complicated situation must be addressed. Any suitable intermediate width \(z\) from a given range of intermediate roll widths \([z_{\min},z_{\max}]\) can be picked. Since every intermediate roll and finished roll is associated with a row of the LP matrix, generating all the feasible intermediate orders whose widths fall within that interval would cause the problem to expand in both directions: columns and rows. Hence, the application of the Column Generation algorithm falls short  
Figure 2: Lexicographic search tree for pattern generation with priorities. since it would not take into account the dual variables of the missing intermediate rolls, and the potentially huge number of intermediate rolls precludes generating all the possible cutting patterns beforehand. Refs. [13; 14; 17] proposed a Row-and-Column Generation (R&CG) algorithm for the One-Dimensional Two-Stage Cutting Stock Problem (1D-TSCSP), which starts from a Relaxed Short and Restricted Master Problem (RSRMP)--an initial model that limits not only the number of decision variables (columns) but also the number of constraints (rows)--and is based on three types of auxiliary subproblems. Specifically, the first auxiliary subproblem generates the cutting patterns for the first stage (columns of \(A_{11}\)), the second generates the cutting patterns for the second stage (columns of \(A_{22}\)), and the third simultaneously generates new intermediate rolls and their associated cutting patterns. This third subproblem involves adding new rows (representing intermediate orders) to the matrices \(A_{11}\) and \(A_{22}\), and new columns to \(A_{11}\), \(A_{12}\), and \(A_{22}\). It requires generating at least one pattern at the first stage that includes the new intermediate orders and a pattern at the second stage that consumes them. In this section, an adapted version of the Row-and-Column Generation algorithm proposed by [15] tailored to the One-and-Half-Dimensional problem is presented. At each iteration, the dual problem of the restricted problem is solved. The dual problem is advantageous in CSPs because it typically has fewer variables than the primal problem--the number of dual variables corresponds to the number of orders, which is a fixed quantity, where \(\mathbf{u}_{1}\) and \(\mathbf{u}_{2}\) are the dual variables associated with the first and second stage constraints, respectively. maximize \[\mathbf{b}_{2}^{T}\mathbf{u}_{2}\] (11) subject to \[A_{11}^{T}\mathbf{u}_{1}\leq\mathbf{c}_{1}\] (13) \[A_{12}^{T}\mathbf{u}_{1}+A_{22}^{T}\mathbf{u}_{2}\leq\mathbf{c} _{2}\] (14) \[\mathbf{u}_{1}\in\mathbb{R}^{m_{1}}\] (15) \[\mathbf{u}_{2}\in\mathbb{R}_{+}^{m_{2}}\] (16)  
Note that \(\mathbf{u}_{1}\) is unrestricted in sign due to the equality constraints in the first stage, and \(\mathbf{u}_{2}\geq\mathbf{0}\) corresponds to the inequality constraints in the second stage.