# Algorithmic Advances for 1.5-Dimensional Two-Stage Cutting Stock Problem
## 4 Solution Approach
### Row-and-Column Generation Algorithm
#### 4.2.3 Row-Generating PSP  
The Row-Generating Pricing Subproblem (RCG-PSP) aims to identify new intermediate rolls as new rows and their associated cutting patterns as new columns that, when added to the RSRMP, expand the feasible solution space and enhance the likelihood of achieving optimality. In the context of the 1.5-D TSCSP, the Row-Generating PSP is particularly challenging due to four main reasons:  
* The lengths of the intermediate rolls are unknown, as are their widths. * The dual variables associated with these new intermediate rolls are not known in advance, except that they are non-negative in any feasible dual solution. These dual variables must be accurately estimated to effectively incorporate them into the solution of the row-generating PSP effectively. * Multiple second-stage cutting patterns can be produced from a single intermediate roll. * Multiple intermediate rolls may need to be generated simultaneously. To address the first challenge, only one first-stage length \(L_{1}\) is considered at a time. Considering Case 3 as presented in the introduction, all intermediate orders generated in the same first-stage pattern must have the same length \(L_{1}\). However, it is not necessary for patterns cut from different intermediate rolls to have the same length. Regarding the estimation of the dual variables for the intermediate orders, the complementary slackness condition from linear programming duality theory can be used. When generating second-stage patterns that reduce the total trim loss--that is, the objective function value of the RSRMP--then the corresponding dual variable for the intermediate roll will take a strictly positive value. This implies that the corresponding dual constraint is tight, i.e., satisfied with equality. Consider an intermediate roll \(k\) and a second-stage cutting pattern \(j\). The corresponding dual constraint from the dual problem is \(-u_{1k}\delta_{kj}+\sum_{i=1}^{m_{2}}u_{2i}A_{22 ij}\leq c_{2j}\). If the constraint is forced to be tight and \(c_{2j}=\gamma_{2j}L_{2}\)where \(\gamma_{2j}\) represents the trim loss for pattern \(j\), and \(\delta_{ij}=\frac{L_{2}}{\ell_{1k}}\), where \(L_{2}\) is the length of the second-stage pattern \(j\), then the dual constraint can be rearranged to solve for \(u_{1k}\): \(u_{1k}=-\gamma_{2j}\ell_{1k}+\frac{\ell_{k}}{L_{2}}\sum_{i=1}^{m_{2}}u_{2i}A_{ 22 ij}\). This consideration is closely related to the third challenge. Since the dual variables \(u_{2i}\) for \(i=1,\ldots,m_{2}\) are positive, as they are associated with demand constraints in the second stage, and the coefficients \(A_{22 ij}\) are non-negative, representing quantities of orders in patterns, each term \(u_{2i}A_{22 ij}\) is positive. Therefore, to generate a new intermediate roll with a negatively priced column, it suffices to consider the second-stage pattern that maximizes \(\sum_{i=1}^{m_{2}}u_{2i}A_{22 ij}\). This means that is sufficient to consider a single second-stage cutting pattern for each new intermediate order. The Row-Generating PSP is formulated for each combination of first-stage length \(L_{1}\) and second-stage length \(L_{2}\), such that their ratio is feasible.