# Algorithmic Advances for 1.5-Dimensional Two-Stage Cutting Stock Problem
## 4 Solution Approach
### Row-and-Column Generation Algorithm
Observe that since each row of the matrix \(A_{12}^{T}\) has only a single non-zero component, the constraint corresponding to each second-stage pattern \(j\) simplifies to \(-\delta_{kj}u_{1k}+\sum_{i=1}^{m_{2}}u_{2i}A_{22 ij}\leq c_{2j}\), where \(k\) is the index of the intermediate order from which pattern \(j\) is produced and \(\delta_{kj}\) is the inverse of the length ratio. Let \(u_{11}^{\star}\) for \(i=1,\ldots,m_{1}\) and \(u_{2i}^{\star}\) for \(i=1,\ldots,m_{2}\) be the optimal dual prices for first and second stage, respectively. To determine whether there exists a constraint, i.e., cutting pattern, not present in the restricted problem that is violated by the current solution, a maximization problem known as the Pricing Subproblem (PSP) must be solved for each stage and subset of compatible orders. As illustrated in Algorithm 2, the procedure encompasses three distinct types of Pricing Subproblems (PSPs):  
* First-Stage Pricing Subproblem (1S-CG-PSP): searches for a new column \(\mathbf{a_{1}}\) of \(A_{11}\) that have negative reduced costs with respect to the current set of constraints in the Relaxed Restricted Master Problem (RSRMP). * Second-Stage Pricing Subproblem (2S-CG-PSP): searches for a new column \(\mathbf{a_{2}}\) of \(A_{22}\) that have negative reduced costs with respect to the current set of constraints in the Relaxed Restricted Master Problem (RSRMP). * Row-Generating Pricing Subproblem (RCG-PSP): searches for new intermediate orders (rows) and their associated columns \(\mathbf{a_{1}}\) and \(\mathbf{a_{2}}\) for \(A_{11}\), \(A_{22}\) and \(A_{12}\). ```
1:FLAG \(\gets 1\)
2: Construct initial RSRMP
3: Solve RSRMP
4:while True do\(\triangleright\) first-stage-pricing
5:for\(L_{1}\) in First Stage Lengths do
6: Solve 1S-CG-PSP
7:endfor
8:if A negatively priced column exists then
9: FLAG \(\gets 1\)
10: Add column(s) to RSRMP
11: Solve RSRMP
12:else
13: FLAG \(\leftarrow\) 0
14:while True do\(\triangleright\) second-stage-pricing
15:for intermediate order \(k\) in Intermediate Orders do
16:for\(L_{2}\) in Second Stage Feasible Lengths do
17: Solve 2S-CG-PSP
18:endfor
19:endfor
20:if A negatively priced column exists then
21: FLAG \(\gets 1\)
22: Add column(s) to RSRMP
23: Solve RSRMP
24:else
25: break
26:endif
27:endwhile
28:if FLAG = 0 then
29:while True do\(\triangleright\) row-generating
30:for\(L_{1}\) in First Stage Lengths do
31:for\(L_{2}\) in Second Stage Feasible Lengths do
32:for\(\alpha^{*}\) in \(1,\ldots,\frac{w_{0}-t_{min,1}}{z_{min}}\)do
33: Solve RCG-PSP
34:endfor
35:endfor
36:endfor
37:if A negatively priced column exists then
38: FLAG \(\gets 1\)
39: Add column(s)/row(s) to RSRMP
40: Solve RSRMP
41:else
42:break
43:endif
44:endwhile
45:if FLAG = 0 then
46: break
47:endif
48:else
49:continue
50:endif
51:endif
52:endwhile
```  
**Algorithm 2** Row-and-Column Generation Algorithm. The algorithm begins by repeatedly solving 1S-CG-PSP. Once no additional first-stage columns can be generated, 2S-CG-PSP is solved to identify new second-stage columns following a similar iterative approach. If neither of the CG-PSPs yield new columns given the current intermediate orders, RCG-PSP is employed. This subproblem potentially introduces both new rows and related columns into the RSRMP. After solving a Pricing Subproblem with at least a negatively priced column, the algorithm returns to the 1S-CG-PSP because the dual variables may have changed due to the addition of new constraints and variables. The algorithm terminates when, in the same iteration, all PSPs do not produce any negatively priced columns--this is indicated when the FLAG variable remains zero. Addressing Case 3 as presented in the introduction, it is necessary to partition the orders at each stage into multiple Pricing Subproblems. Each PSP consists of orders that share the same length within the same stage and have the same length ratio between different stages. This partitioning ensures compatibility among the orders within each PSP and allows us to effectively apply the Row-and-Column Generation algorithm.