## 3 Materials and Methods
### Generation of Cutting Patterns  
The task of generating all cutting patterns is computationally expensive, since the quantity \(n\) of patterns can be extremely large. The greater the variability of the length of the items and the smaller these items are in relation to the object size, the greater is the complexity of this task. In what follows, we resort to a procedure for generating cutting patterns proposed by [PERSON] [31] and propose a strategy employed to artificially reduce the amount of patterns considered into the ILP formulation.  
Consider an example in which the identical objects of length \(L=100\) and a set of \(m=3\) different types of items are given. The procedure starts by sorting the items in descending order of length \(l_{i}\), \(i=1,2,\ldots,m\). In the running example, assume \(l_{1}=50\), \(l_{2}=30\), and \(l_{3}=20\). An \(m\)-ary search tree is used to illustrate the pattern generation procedure, as presented in Figure 2. The root node (in orange) represents the length of the large object, the internal nodes (in blue) represent the length of the items, and the leaf nodes (in red) indicate a cut loss. Any path from the root node down to a leaf represents a cutting pattern.  
Starting from the root node, the procedure recursively includes as a new branch every item that can be obtained from the residual length of the object. If it is no longer possible to include any of the items as a new branch of a given node, the leaf node is created, indicating the cut loss of the cutting pattern defined. The implementation, however, is optimised as in [31] so that the height of the search tree is limited to the number \(m\) of different types  
Figure 1: Generate-and-solve framework.  
of items. In addition, in every cutting pattern, we limit the number of items of each type to their corresponding demand, because this reduces the search space of the continuous relaxation in instances where the demands are small.  
In the running example, there exist \(n=7\) cutting patterns, depicted in the search tree, from left to right: \(a_{1}=(2,0,0)^{T}\), \(a_{2}=(1,1,1)^{T}\), \(a_{3}=(1,0,2)^{T}\), \(a_{4}=(0,3,0)^{T}\), \(a_{5}=(0,2,2)^{T}\), \(a_{6}=(0,1,3)^{T}\) e \(a_{7}=(0,0,5)^{T}\). The patterns \(a_{2}\) and \(a_{4}\) are illustrated in Figure 2(a,b, respectively.  
The number \(n\) of cutting patterns can grow exponentially according to the number \(m\) of item types, and, therefore, the large number of cutting patterns generally makes computation infeasible. To cope with this issue, we propose to limit the generation to a maximum number \(M\) of cutting patterns. More precisely, a maximum number \(\mu_{i}\) of cutting patterns beginning with a given type of item \(i\) is computed as follows:  
\[\mu_{i}=\left\lfloor M\times\frac{m-i+1}{X}\right\rfloor,\text{ where }X=\sum_{i=1}^{m}i.\]  
The recursive procedure to construct the search tree follows a depth-first strategy and includes the branches of a given node according to the ordering of the items. A new branch is added only if the \(\mu_{i}\) limit has not been reached for patterns beginning with type of item \(i\).  
In the running example, consider the value of \(M=6\). As we have \(m=3\), \(X=1+2+3=6\), \(\mu_{1}=\left\lfloor 6\times(3-1+1)/6\right\rfloor=3,\mu_{2}=\left\lfloor 6 \times(2-1+1)/6\right\rfloor=2,\mu_{3}=\left\lfloor 6\times(1-1+1)/6 \right\rfloor=1\). In Figure 2, only the cutting patterns represented in solid lines are actually generated in the search tree. The branch represented in dashed lines is, in turn, pruned down. In this example, the cutting patterns \(a_{6}\) is discarded.  
Figure 3: Examples of cutting patterns. The items are drawn in blue and the cut loss is drawn in red. In (**a**), we illustrate the cutting pattern \(a_{2}\) with cut loss equal to 0 and, in (**b**), the cutting pattern \(a_{4}\) with cut loss equal to 10.  
Figure 2: Example of a cutting pattern search tree.