# Algorithmic Advances for 1.5-Dimensional Two-Stage Cutting Stock Problem
## 4 Solution Approach
### Generate-and-Solve Algorithm
* PatternGenAttempts and OrderGenAttempts: Counters for the remaining attempts in each phase before switching or terminating. These are initialized to a maximum value (MaxAttempts). * UpdateLimit: A predefined threshold for considering an iteration successful, based on the relative improvement in the objective function. At each iteration, after solving the RSRMP, the algorithm evaluates the improvement in the objective value. If the improvement exceeds UpdateLimit, the iteration is considered successful, and the corresponding attempt counter is reset. If not, the attempt counter is decremented. When the attempt counter reaches zero, the algorithm switches phases or terminates if both counters reach zero. To manage the size of the RSRMP and maintain computational efficiency, the countdown value for the patterns used in the current solution is increased by 1, reinforcing their relevance in future iterations; instead, for the unused patterns, this is decremented by 1.Patterns with a countdown value of 0 are removed from the coefficients matrix \(A\). Orders that no longer have associated patterns are also removed. By iteratively refining the set of patterns and intermediate orders considered in the RSRMP, the algorithm converges to high-quality solutions without the need to enumerate all possible combinations upfront. The ability to dynamically introduce new intermediate orders allows the algorithm to escape local optima and explore a broader solution space than methods that only generate patterns. ```
1: Construct initial RSRMP
2:OptimalObj \(\leftarrow+\infty\)
3:Improvement \(\leftarrow\) 0
4:PatternGenIter \(\leftarrow\) True
5:PatternGenAttempts \(\leftarrow\) MaxAttempts
6:OrderGenAttempts \(\leftarrow\) MaxAttempts
7:while True do
8: Solve RSRMP
9: Update CurrentObj
10: Improvement \(\gets 1-\frac{\text{CurrentObj}}{\text{OptimalObj}}\)
11:ifPatternGenIter then
12:ifImprovement \(\leq\) UpdateLimit then
13:PatternGenAttempts \(\leftarrow\) PatternGenAttempts \(-\) 1
14:ifPatternGenAttempts \(=\) 0 then
15:PatternGenIter \(\leftarrow\) False
16:endif
17:else
18:PatternGenAttempts \(\leftarrow\) MaxAttempts
19:endif
20:else
21:ifImprovement \(\leq\) UpdateLimit then
22:OrderGenAttempts \(\leftarrow\) OrderGenAttempts \(-\) 1
23:ifOrderGenAttempts \(=\) 0 then
24:break
25:endif
26:else
27:OrderGenAttempts \(\leftarrow\) MaxAttempts
28:PatternGenAttempts \(\leftarrow\) MaxAttempts
29:PatternGenIter \(\leftarrow\) True
30:endif
31:endif
32:ifPatternGenIter then
33:Update pattern usage counters
34: Remove obsolete column(s) from RSRMP
35: Remove rows with no linking constraints from RSRMP
36: Generate and Add column(s) to RSRMP
37:else
38: Select worst second-stage pattern
39: Generate and Add new row to RSRMP
40: Generate and Add column(s) to RSRMP
41:endif
42:endwhile
```  
**Algorithm 1** Generate-and-Solve Generation Algorithm. The advantages of this approach are manifold:  
**Algorithm Efficiency**: It mitigates combinatorial explosion by restricting patterns and orders, and using a countdown mechanism to remove unused patterns. **Computational Resource Allocation**: Priority-based exploration ensures efficient allocation of resources, focusing on patterns with the highest potential for improvement.