# Algorithmic Advances for 1.5-Dimensional Two-Stage Cutting Stock Problem
## 4 Solution Approach
### Generate-and-Solve Algorithm  
In this section, the implementation of the Generate-and-Solve (G&S) framework applied to the 1.5-D TSCSP is presented. The proposed approach adapts the traditional G&S method, originally designed for one-dimensional CSPs [19], to address the additional complexities introduced by the multi-dimensional and multi-stage nature of the problem, such as the rolls produced in the first stage that serve as input for the second stage. Our algorithm operates by alternating between two primary phases:  
* Pattern Generation Iterations: In this phase, the algorithm focuses on generating new cutting patterns for both the first and second stages without altering the set of intermediate orders. The goal is to improve the current solution by exploring new combinations of existing orders. * Order Generation Iterations: When pattern generation no longer yields significant improvements, the algorithm transitions to this phase, where new intermediate orders are introduced. By expanding the set of intermediate orders, the solution space gets enlarged, allowing for potentially better solutions that were not possible with the previous set of orders. At each iteration, a Relaxed Short and Restricted Master Problem (RSRMP) is solved, which includes only a limited set of cutting patterns and intermediate orders, making it computationally feasible to solve repeatedly within the iterative framework. The algorithm initializes with an initial set of existing first-stage and second-stage patterns and intermediate orders. Each cutting pattern has an associated countdown integer value, which determines its lifespan in the algorithm based on recent usage. Patterns that are not utilized in recent iterations are gradually phased out through the aging mechanism to maintain computational efficiency and prevent the model from becoming too large. Dedicated pattern generators for the first and second stages are responsible for creating new patterns when needed. These pattern generators utilize a lexicographic search tree to systematically explore potential patterns. A priority queue manages the exploration of the pattern generation trees, prioritizing nodes based on their potential to improve the solution. Each node in the search tree represents a partial pattern, containing information about the currently used width, the level in the tree, the remaining width, and the set of remaining orders that can be added to the pattern, determined by lexicographic ordering and feasibility based on residual width. Nodes are prioritized based on trim loss, ensuring a depth-first exploration. When generating child nodes, feasible orders are added to the current pattern, respecting width constraints, one unit at a time. The remaining width is updated accordingly, and the set of remaining orders is adjusted to consider only orders that have not yet been included and fit within the residual width. In the order generation iterations, the algorithm introduces new intermediate orders to expand the solution space. This is a significant difference from the standard G&S method, which typically does not alter the set of items (orders) but focuses on pattern generation. The algorithm identifies inefficient second-stage patterns that contribute most to trim loss and negatively impact the objective function. Based on these patterns, new intermediate orders are created with dimensions designed to reduce waste. The pattern generators are then updated to include these new intermediate orders, allowing the generation of new patterns that incorporate them. When a new intermediate order is introduced, it is added to the leftmost branch of the search tree with maximum priority to ensure it is explored promptly in subsequent iterations. The pseudocode for the Generate-and-Solve algorithm is presented in Algorithm 1. The algorithm employs several parameters to control its execution:  
* PatternGenIter: A boolean flag indicating whether the current iteration is a pattern generation iteration (True) or an order generation iteration (False).