# Algorithmic Advances for 1.5-Dimensional Two-Stage Cutting Stock Problem
## 3 Problem Formulation
### Multi-Stage Master Problem  
Let \(\mathbf{c}^{T}=\left(\mathbf{c}_{1}^{T}\quad\mathbf{c}_{2}^{T}\quad\cdots \quad\mathbf{c}_{S}^{T}\right)^{T}\) be the global cost vector, where \(S\) is the number of stages. Each \(\mathbf{c}_{s}\) for \(s=1,\ldots,S\) is the cost vector specific to the \(s\)-th stage, with \(n_{s}\) components, where \(n_{s}\) is the number of cutting patterns at the \(s\)-th stage. Similarly, let \(\mathbf{b}^{T}=\left(\mathbf{b}_{1}^{T}\quad\mathbf{b}_{2}^{T}\quad\cdots \quad\mathbf{b}_{S}^{T}\right)^{T}\) be the global minimum demand vector. Each \(\mathbf{b}_{s}\) for \(s=1,\ldots,S\) is the minimum demand vector specific to the \(s\)-th stage, with \(m_{s}\) components, where \(m_{s}\) is the number of orders at the \(s\)-th stage. For the intermediate orders, the demand is set to zero, representing that no minimum quantity needs to be produced beyond consumption. The global decision variable is the vector \(\mathbf{x}^{T}=\left(\mathbf{x}_{1}^{T}\quad\mathbf{x}_{2}^{T}\quad\cdots \quad\mathbf{x}_{S}^{T}\right)^{T}\), where each \(\mathbf{x}_{s}\) indicates how many times each pattern at stage \(s\) is used in the solution. The model in matrix form is shown below:  
minimize \[\mathbf{c}^{T}\mathbf{x}\] (1) subject to \[A\ \mathbf{x}\geq\mathbf{b}\] (2) \[\mathbf{x}\in\mathbb{Z}_{+}^{n}\] (3)  
Here, \(n=\sum_{s=1}^{S}n_{s}\) is the total number of cutting patterns across all stages. The constraint matrix \(A\) has a special block structure, reflecting the relationships between stages and patterns. Each element \(A_{s_{1}s_{2}}\) is a sub-matrix of dimensions \(m_{s_{1}}\times n_{s_{2}}\), with \(s_{1},s_{2}=1,\ldots,S\). \[A= \begin{pmatrix}A_{11}&A_{12}&\cdots&A_{1S}\\ A_{21}&A_{22}&\cdots&A_{2S}\\ \vdots&\vdots&\ddots&\vdots\\ A_{S1}&A_{S2}&\cdots&A_{SS}\end{pmatrix}  \tag{4}\]The matrices \(A_{s_{1}s_{2}}\) represent the interactions between orders at stage \(s_{1}\) and patterns at stage \(s_{2}\). Specifically, these are as follows:  
* The diagonal blocks \(A_{ss}\) for \(s=1,\ldots,S\) are the canonical cutting stock matrices for the \(s\)-th stage. Each column in \(A_{ss}\) corresponds to a cutting pattern at stage \(s\), and each row corresponds to an order at that stage. The element \(A_{ssij}\) indicates the quantity of order \(i\) produced by pattern \(j\). * The off-diagonal blocks \(A_{s_{1}s_{2}}\) for \(s_{1}\
eq s_{2}\) represent the consumption of intermediate stock rolls between stages. These blocks are called _connection matrices_. For \(s_{1}<s_{2}\), \(A_{s_{1}s_{2}}\) captures the consumption of stock rolls from stage \(s_{1}\) by patterns at stage \(s_{2}\). Each column in a connection matrix \(A_{s_{1}s_{2}}\) represents a pattern at stage \(s_{2}\), and each element indicates the consumption of an intermediate roll from order \(i\) at stage \(s_{1}\) by pattern \(j\) at stage \(s_{2}\). This consumption is quantified by \(-\delta_{ij}\), where \(\delta_{ij}\) is the fraction of the intermediate roll consumed by one use of pattern \(j\). For example, if the intermediate roll from order \(i\) at stage \(1\) has a length of \(\ell_{1,i}=8000\) m, and a pattern \(j\) at stage \(2\) produces rolls of length \(\ell_{2,j}=2000\) m, then the consumption is \(\delta_{ij}=\frac{\ell_{2,j}}{\ell_{1,i}}=0.25\). This means that four uses of pattern \(j\) are necessary to consume an entire intermediate roll from order \(i\). Let the length ratio be \(\beta_{ij}=\frac{\ell_{1,i}}{\ell_{2,i}}=\frac{1}{\delta_{ij}}\). This ratio indicates how many times a pattern at the downstream stage can be applied to fully consume an intermediate roll from the upstream stage. Without loss of generality, let \(A_{s_{1}s_{2}}=\mathbf{0}\) when \(s_{1}>s_{2}\), because conversion flows from downstream to upstream are not practical and are not permitted due to possible treatments applied to the items. This block structure of the constraint matrix allows us to capture the material flow and dependencies between stages in the multi-stage CSP.