# Algorithmic Advances for 1.5-Dimensional Two-Stage Cutting Stock Problem
###### Abstract  
The Cutting Stock Problem (CSP) is an optimization challenge that involves dividing large objects into smaller components while considering various managerial objectives. The problem's complexity can differ based on factors such as object dimensionality, the number of cutting stages required, and any technological constraints. The demand for coils of varying sizes and quantities necessitates intermediate splitting and slitting stages to produce the finished rolls. Additionally, relationships between orders are affected by dimensional variations at each stage of processing. This specific variant of the problem is known as the One-and-a-Half Dimensional Two-Stage Cutting Stock Problem (1.5-D TSCSP). To address the 1.5-D TSCSP, two algorithmic approaches were developed: the Generate-and-Solve (G&S) method and a hybrid Row-and-Column Generation (R&CG) approach. Both aim to minimize total trim loss while navigating the complexities of the problem. Inspired by existing problems in the literature for simpler versions of the problem, a set of randomly generated test cases was prepared, as detailed in this paper. An implementation of the two approaches was used to obtain solutions for the generated test campaign. The simpler G&S approach demonstrated superior performance in solving smaller instances of the problem, while the R&CG approach exhibited greater efficiency and provided superior solutions for larger instances. According to the typology proposed in [1] and the refined classification discussed in [2], the development of slitting programs falls within the expansive optimization domain of cutting and packing problems. These problems are fundamentally characterized by two core entities: stock objects that represent input and items that represent demand. Specifically, by integrating dimensionality, assignment, and assortment, this problem can be succinctly represented by the 1.5/V/I/R tuple or as a 1.5-D rectangular SSSCSP. In particular, the assignment of dimensionality in this context deviates from conventional interpretations. As described in [3; 4], traditional two-dimensional problems account for width and length as degrees of freedom in the generation of cutting patterns. In contrast, the One-and-a-Half-Dimensional (1.5-D) problem constructs patterns by combining items (or final orders) based on their width, analogous to a one-dimensional problem. However, the number of feasible patterns is constrained by the length of the input rolls. Specifically, the length of a pattern corresponds to the length of the orders cut in that particular combination, and patterns can be generated only until the total length of the input roll is exhausted. Consequently, the second dimension functions partially as a production constraint rather than a degree of freedom in the pattern generation process. The shapes of both items and objects are rectangular, and their orientation is fixed. As a result, the items must align adjacently, akin to the two-dimensional problem with guillotine cuts in the exact case, but only along their shorter edges. The objective, therefore, is to combine orders in both the transverse and longitudinal directions of the slitter, subject to length constraints. These constraints are intrinsically linked to the availability of stock rolls and the capability to slit rolls of varying lengths within the same setup, which are restricted to a discrete set of predefined values. Taking into account these factors, this problem can be classified as a One-and-a-Half Two-Stage Cutting Stock Problem (1.5-D TSCSP). The relationships between orders are influenced not only by the transitions between stages but also by the varying lengths within the same stage. The following scenarios may arise:  
* Case 1: The first and second stages have the same length. This scenario reduces to a one-dimensional problem, which has been extensively studied in the literature. * Case 2: Only one length is present in the first stage and only one length at the second stage, but they are different.