# Algorithmic Advances for 1.5-Dimensional Two-Stage Cutting Stock Problem
## 3 Problem Formulation  
The addressed problem pertains to a cutting process involving \(S\) stages. At each stage \(s\), a set of \(m_{s}\) final orders is generated. Each order is associated with a minimum demand \(b_{si}\) for rolls of width \(w_{si}\) and length \(\ell_{si}\). The objective is to determine, for each stage \(s\), the set of \(n_{s}\) cutting patterns \(\mathbf{a}_{sj}\) and their corresponding quantities \(x_{sj}\), such that the trim loss in width \(\gamma_{sj}\) is greater than or equal to the minimum allowable \(t_{min,s}\). Each pattern \(\mathbf{a}_{sj}\) is a vector consisting of \(m_{s}\) components, where each component \(i\) indicates the number of times order \(i\) is produced in that cutting pattern. All orders with a positive entry have the same length \(\ell_{sk}\). Additionally, the intermediate orders \(k\) at each stage \(s=1,\ldots,S-1\) must be determined through splitting and feeding the subsequent stages \(t=s+1,\ldots,S\), specifying their widths \(w_{sk}\) within an interval \([z_{min,st},z_{max,st}]\) and their lengths \(\ell_{sk}\) selected from a set \(\mathcal{B}_{st}\) of feasible length ratios. The objective is to minimize the total trim loss \(\sum_{s=1}^{S}\sum_{i=1}^{n_{s}}c_{sj}x_{sj}\), where \(c_{sj}\) is the trim area, i.e., the product of the trim width \(\gamma_{sj}\) and the pattern length \(\ell_{sk}\). In addition, the first stage is assumed to always use a single mill roll of a fixed width \(W\) and unlimited supply, and that for each stage \(s\), there is no initial stock for each intermediate order \(k\); therefore, the total length produced must be greater than or equal to the length consumed by the subsequent stages. For simplicity, final orders are assumed to be present only at the last stage. Afterwards, the problem with only two stages is formulated and the total quantity produced of each intermediate order is forced to be entirely consumed.  
The problem stated will be formulated as a Cutting Stock Problem, which is well known to be NP-Hard, where a sufficiently large inventory of single fixed width mill rolls, which serve as input for the first cutting stage, are first split into intermediate stock rolls, and each of them is then slit to produce finished rolls, meeting the minimum demand across all orders. Due to technological constraints, it is not feasible to convert the entire width of the mill roll, resulting in trim loss, which constitutes the primary source of waste in the process. Trim loss is typically divided into two types: fixed and variable. The fixed component is unavoidable and cannot be eliminated, while the variable component depends on the quality of the optimization. In practical applications, treatments are applied to the produced rolls, making the minimization of intermediate orders secondary to the need to minimize trim loss, expressed in units of surface area. This surface area is the product of the pattern length and the trim width, contrasting with the formulation by [13; 17], which minimizes the number of first-stage patterns used.  
A comprehensive formulation that encapsulates the intricacies of multiple cutting stages is presented in the following section. This extended set-covering approach integrates the interactions between various stages, ensuring that intermediate orders are optimally managed throughout the production flow. In this formulation, a cost coefficient is associated with each cutting pattern, and an integer decision variable represents the number of times each pattern is utilized. The following subsections provide a detailed description of the structure and components of the general Multi-Stage CSP, as well as its specialization to the Two-Stage version. This version will be explored further through the application of the Row-and-Column generation algorithm and an adapted version of the Generate-and-Solve method.