# 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
maximize \[\sum_{i=1:\ell_{1i}=L_{1}}^{m_{1}}u_{1i}^{\star}a_{1i}+\sum_{k=1:\ell_{1i}=L_ {1}}^{K}v_{k}^{\star}\alpha_{k}-\gamma_{1}L_{1}\] (27) subject to \[\gamma_{1}=w_{0}-\sum_{i=1:\ell_{1i}=L_{1}}^{m_{1}}w_{1i}a_{1i}- \sum_{k=1:\ell_{1k}=L_{1}}^{K}z_{k}\alpha_{k}\] (28) \[\gamma_{1}\geq t_{min,1}\] (29) \[a_{1i}\geq 0,\text{integer} \forall i=1,\ldots,m_{1}:\ell_{1i}=L_{1}\] (30) \[a_{k}\geq 0,\text{integer} \forall k=1,\ldots,K\] (31) \[z_{min}\leq z_{k}\leq z_{max},\text{integer} \forall k=1,\ldots,K\] (32) where \[v_{k}^{\star}=\max\quad\sum_{i=1:\ell_{2i}=L_{2}}^{m_{2}}u_{2i}^{ \star}a_{2 ki}-\gamma_{2k}L_{1}\] (33) subject to \[\gamma_{2k}=z_{k}-\sum_{i=1:\ell_{2i}=L_{2}}^{m_{2}}w_{2i}a_{2 ki}\] (34) \[\gamma_{2k}\geq t_{min,2}\] (35) \[a_{2 ki}\geq 0,\text{integer} \forall i=1,\ldots,m_{2}:\ell_{2i}=L_{2}\] (36) \[\gamma_{1}=w_{0}-\sum_{i=1:\ell_{1i}=L_{1}}^{m_{1}}w_{1i}a_{1i}- \sum_{k=1:\ell_{1k}=L_{1}}^{K}z_{k}\alpha_{k}\]0 (37)  
Here, \(\alpha_{k}\) is the decision variable corresponding to the number of times the new intermediate order \(k\) is included in the first-stage cutting pattern and \(z_{k}\) its width. \(\gamma_{1}\) and \(\gamma_{2k}\) represent the trim losses at the first and second stages. The new columns and rows generated are incorporated into the RSRMP's coefficient matrix \(A\) as follows:  
* \(\mathbf{a}_{1}{}^{\star}\) is the new column corresponding to the first-stage cutting pattern. * \(\mathbf{a}_{2k}^{\star}\) is the new column corresponding to the second-stage cutting pattern produced from intermediate order \(k\). * \(\alpha_{k}^{\star}\) is included to account for the number of times the intermediate order \(k\) is used in the newly created first-stage cutting pattern. * \(-\frac{\ell_{2k}}{L_{1}}\) is the non-zero term placed at the position corresponding to the intermediate order \(k\) in the linking constraint row. \[A=\left( \begin{array}{cccccccc}A_{11}&{\bf a_{1}}^{\star}&A_{12}&{\bf 0}& \ldots&{\bf 0}\\ {\bf 0}^{T}&\alpha_{1}^{\star}&{\bf 0}^{T}&-\frac{f_{21}}{T_{1}}&\ldots&0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ {\bf 0}^{T}&\alpha_{K}^{\star}&{\bf 0}^{T}&0&\ldots&-\frac{f_{2K}}{L_{1}}\\ O&{\bf 0}&A_{22}&{\bf a}_{21}^{\star}&\ldots&{\bf a}_{2K}^{\star}\end{array} \right) \tag{38}\]  
Regarding the fourth challenge, although multiple intermediate rolls may need to be generated simultaneously, the problem can be simplified by generating one intermediate roll at a time. This approach, inspired by [PERSON]'s simplification [13], reduces the computational complexity and has been shown to be effective in practice [17]. By focusing on generating a single intermediate roll per iteration, a unified mathematical model can be formulated. However, this model remains challenging to solve because it would take the form of a nonlinear integer knapsack problem due to the product terms involving \(z\) and \(\alpha\) and \(a_{2i}\) and \(\alpha\). As suggested in the literature [14], the problem can be further simplified by fixing the value of \(\alpha\). By iterating over possible integer values of \(\alpha^{\star}\) within a feasible range, the nonlinear knapsack problem can be transformed into several linear knapsack problems, which are easier to solve. This approach significantly reduces the computational complexity and allows for an efficient exploration of potential intermediate rolls.