## 3 Materials and Methods
### Application of the Generate-and-Solve  
Reduced instances of the 1D-CSP can be obtained by considering only a subset of the decision variables of the original problem instance, that is, only a subset of the feasible cutting patterns. The reduced instance is, therefore, an ILP model containing all the constraints present in the problem formulation, but only a subset of the cutting patterns, as in the CG technique. The choice of the subset of cutting patterns, however, is performed through a metaheuristic engine. To explain the representation of a reduced instance, we refer to the running example discussed previously. Recall that, in order to deal with large sized instances of the problem, we employ a strategy for reducing the number of patterns. Thus, in Figure 4, we represent only the cutting patterns that were not discarded when applying this strategy. The representation of a reduced instance of the problem is performed using an array of integers. Each position in the array is associated with a cutting pattern in the search tree. In this representation, a value greater than or equal to 1 (one) indicates that the associated cutting pattern (decision variable) is considered in the reduced instance (ILP model). Conversely, a value of 0 (zero) indicates that the associated cutting pattern is not taken into account in the reduced instance. In addition, the value is used as an aging mechanism [25] to control the growth of reduced instances. Whenever a new cutting pattern is incorporated into the reduced instance, its age is set to 1 (one) and, at each iteration of the G&S method, the age of every cutting pattern that is part of the reduced instance is increased by 1 (one). If the age of a cutting pattern reaches a maximum age value \(\alpha\), the value is reset to 0 (zero), that is, the pattern is removed from the reduced instance to prevent unpromising cutting patterns from unnecessarily impacting the efficiency of the ILP solver. However, whenever a cutting pattern is effectively used in the solution returned by the ILP solver, its age is reset to 1 (one) to ensure that this pattern is considered in the next \(\alpha\) iterations of the G&S method. In order to obtain an initial reduced instance that produces a feasible solution when submitted to the ILP solver, the following greedy strategy was adopted to select the cutting patterns. Considering the cutting pattern search tree from left to right, the current cutting pattern is added to the instance under construction if it contains an item that has not yet been covered by any other pattern. The process continues until all items have been covered by the patterns added to the instance. Then, the reduced instance is submitted to the SRI to obtain an initial solution. From then on, the aging mechanism guarantees the existence of a feasible  
Figure 4: In the representation of reduced instances of the problem, each position in the array is associated with a cutting pattern in the search tree. The cutting patterns considered in the reduced instance present a value greater than or equal to 1 (one) in the array and are highlighted in green in the search tree. In (**a**), we illustrate a reduced instance with all cutting patterns from the search tree and, in (**b**), a reduced instance with only 4 cutting patterns. solution in all reduced instances submitted to the SIR. In addition, at each iteration of the G&S method, the current instance contains a solution that is at least as good as the previous ones. For the GRI, a simple hill climbing algorithm was implemented, as illustrated in Algorithm 1. A neighbour instance is obtained from the application of a mutation operator. Considering a mutation rate \(\rho\), the mutation operator, when effectively applied to a position of the array, modifies the value to 1 (one) whenever the original value is 0 (zero), and, conversely, modifies the value to 0 (zero) whenever the original value is greater than 1 (one).