# Cutting stock problem with usable leftovers: A review

Victor Senergues, Nadjib Brahimi, Adriana Cristina Cherri, François Klein, Olivier Péton

<figure><img src="image_1.png" /></figure>

## To cite this version:

Victor Senergues, Nadjib Brahimi, Adriana Cristina Cherri, François Klein, Olivier Péton. Cutting stock problem with usable leftovers: A review. European Journal of Operational Research, In press, 10.1016/j.ejor.2025.03.014. hal-05086760

HAL Id: hal-05086760

https://hal.science/hal-05086760v1

Submitted on 27 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
<figure><img src="image_3.png" /></figure>

Invited Review

Cutting stock problem with usable leftovers: A review

Victor Senergues<sup>a,b,d</sup>, Nadjib Brahimi<sup>c,d,*</sup>, Adriana Cristina Cherri<sup>e,f</sup>, François Klein<sup>b</sup>,
Olivier Péton<sup>a,d</sup>

ARTICLE INFO

Keywords:

Cutting problems

Usable leftovers

Optimization

Survey

A B S T R A C T

This article presents a comprehensive literature review of the Cutting Stock Problem with Usable Leftovers (CSPUL). The most recent review on this topic dates to 2014, covering articles published before 2013. Since then, the number of publications on CSPUL has increased significantly, driven by new applications and more efficient solution approaches. We analyze fifty two relevant articles from twenty four different journals, focusing on works published after 2008 while acknowledging foundational contributions from the 1980s and 1990s. This review categorizes variations of CSPUL based on their dimensions (1D, 2D, and 3D), planning period characteristics (single-period and multi-period), objective functions, and solution methods. The article provides a detailed summary of the key features in the mathematical models and solution methods proposed in these studies. Additionally, it highlights several industrial applications of CSPUL, illustrating its practical relevance. Through this analysis, we identify important applications and propose promising directions for future research. The findings and insights presented here have practical implications for optimizing resource utilization and promoting sustainability in industries facing cutting challenges.

# 1. Introduction

The cutting stock problem (CSP) has long been an important topic in the academic operations research community and for practitioners. Since the seminal paper by Gilmore and Gomory (1961), hundreds of papers have been published on the CSP and its wide range of extensions and applications (Cheng et al. 1994, Lodi et al. 2002, De Carvalho 2002, Delorme et al. 2016, among others). Most of these studies have focused on minimizing waste during the cutting process. However, a recent trend has been to consider the possibility of generating usable leftovers during the cutting process. Since a leftover exceeds a certain size, it returns to stock as a retail and can be used to fulfill future orders of items. This is relevant to several industries concerned with cutting metals (Gracia et al., 2013), wood (Parreño & Alvarez-Valdes, 2021), clothes (Gradišar et al., 1997), and other materials.

According to Cherri et al. (2009), the extension of the CSP that considers the possibility of generating usable leftovers is known as the cutting stock problem with usable leftovers (CSPUL). The emergence of the CSPUL coincided with greater economic and environmental

pressures on the industries. While CSP minimizes the leftovers, without relying on their possible use, the CSPUL has a longer-term vision, and favors the future use of leftovers. For example, instead of generating multiple leftovers that are too small (waste) to be exploitable, the CSPUL tends to generate fewer and larger size leftovers with greater potential. The idea behind adopting the leftovers from the cutting process is generating less waste to the environment, less transportation, less recycling energy, and greater profits. In addition, several raw materials are produced, for which recycling is expensive and not economically viable.

In a basic definition, the CSPUL consists of producing a set of
demanded items by cutting available objects bought from suppliers
(standard objects) or retails (usable leftovers) from previous cuts. Using
the available objects and retails from the stock, the demand must be
met by minimizing the waste or optimizing another objective func-
tion. In this problem, usable leftovers can be generated in predefined
amounts and sizes. In Arenales et al. (2015) the authors pointed out
that retails must be generated only if the waste is minimized.

<footnote><sup>a</sup> IMT Atlantique, 4 rue Alfred Kastler, 44307, Nantes, France</footnote>

<footnote><sup>b</sup> Reversé Systems, 3 place Albert Camus, 44200, Nantes, France</footnote>

<footnote><sup>c</sup> Rennes School of Business, 2 rue Robert d'Arbrissel, 35065, Rennes, France</footnote>

<footnote><sup>d</sup> Laboratoire des Sciences du Numerique de Nantes (LS2N, UMR CNRS 6004), France</footnote>

<footnote><sup>e</sup> Faculdade de Ciências, Universidade Estadual Paulista, Bauru SP, Brazil</footnote>

<footnote><sup>f</sup> INESC TEC, Portugal</footnote>

<footnote>* Corresponding author.
*E-mail addresses:* victor.senergues@reverse-systems.com (V. Senergues), nadjib.brahimi@rennes-sb.com (N. Brahimi), francois.klein@reverse-systems.com (F. Klein), olivier.peton@imt-atlantique.fr (O. Péton).</footnote>
<figure><img src="image_4.png" /><figcaption>**Fig. 1.** Distinction between a usable leftover (green) and waste (gray) after cutting items (in blue). The usable leftover is later used to cut additional items in (a) and (b). (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)</figcaption></figure>

Figs. 1(a) and (b) illustrate the 1D-CSPUL and 2D-CSPUL, respectively. In Fig. 1(a), two objects (pipes) are cut into several items (blue items). The first pipe generates a small waste (in gray), whereas the second generates a retail (in green) that can be used later to generate two items and a small waste. A similar analysis can be made in Fig. 1(b).

Compared to the CSP, the CSPUL presents economic and ecological advantages but generates new challenges for academia and practitioners. More complex planning processes are required for the effective management of leftovers and waste disposal. Furthermore, it is important to discuss the trade-offs between the resulting benefits and the incurred costs related to material handling and inventory. Motivated by the increasing number of publications on the CSPUL and its importance in industry, a comprehensive and updated review of the literature is necessary.

Several literature reviews have been published on the CSP and its extensions. For example, Cheng et al. (1994) discussed classical 1D and 2D CSP. Their focus was on the 2D problems and their links with other problems, such as packing and pallet loading problems. Melega et al. (2018) proposed a survey and classification of studies on the integration of CSP and lot-sizing problems (LSP). The paper briefly cites publications on the CSPUL to highlight interest in exploiting usable leftovers in integrated LSP/CSP models in future research. In the literature review on operations scheduling to minimize waste, Le Hesran et al. (2019) briefly mentioned usable leftovers. CSPs with uncertainty were surveyed by Hadj Salem et al. (2023). The authors classified the uncertainty in CSPs based on their source (defects, availability, etc.) and their representation (discrete, continuous). To the best of our knowledge, Cherri et al. (2014) conducted the only survey on the CSPUL, looking for 1D-CSPUL publications up to 2013. Our literature review will contribute to an updated review of the 1D-CSPUL including variants regarding the two and three-dimensional problems (denoted by 2D-CSPUL and 3D-CSPUL, respectively) and their challenges.

The research of this paper will contribute to the literature by presenting a comprehensive and current literature review of the CSPUL considering 1D, 2D and 3D cases, and also: (1) it presents key elements of the mathematical programming formulations of 1D and 2D problems, (2) it classifies the reviewed publications based on the different objectives and constraints, (3) it discusses the different solution approaches used to solve the CSPUL, (4) it discusses the main challenges related to the management of leftovers in industries, (5) it explores and synthesizes real-world applications of the CSPUL emphasizing industry-specific challenges, and (6) it outlines future research directions.

In the remainder of this paper, Section 2 presents two mathematical programming formulations that are the 1D-CSPUL and 2D-CSPUL. Four important features of the CSPUL are reviewed in Section 3: the modeling approach (item- or pattern- based), type of objective function considered, the number of periods considered, and type of cut.

In Section 4, we review solution methods for the CSPUL. Section 5 describes the industrial applications. A general discussion is presented in Section 6. Finally, Section 7 summarizes the main findings and presents future research avenues.

## 2. Problem description and formulations

The cutting stock problem with usable leftovers is a challenging combinatorial optimization problem. In the same way that the CSP is classified as NP-hard in the strong sense, the CSPUL is also NP-hard in the strong sense (Garey & Johnson, 1979; Martello et al., 2003). Besides being a complex problem to be solved, when the problem involves more than one dimension, the cutting patterns are more complex to be elaborated, because is necessary to deal with difficulties related to geometry, non-overlap, and containment of items within the object to be cut. In the cutting problems, cutting pattern defines a subset of items cut from an object.

The problem can be modeled as item-oriented or pattern-oriented. The item-oriented models individually consider every item to be cut. In pattern-oriented models, items are grouped into feasible patterns and the models explicitly look for how often each pattern should be cut to satisfy demand.

In the rest of this section, we will discuss one mathematical programming formulation for the 1D-CSPUL and another for the 2D-CSPUL. The 1D formulation was the first study to address and solve the usable leftovers explicitly. The 2D formulation was also the first to deal with usable leftovers.

### 2.1. 1D-CSPUL formulation

In the CSPUL a set of demanded items $d_i, i = 1, ..., m$ must have their demand satisfied by cutting $s$ types of standard objects, $s = 1, ..., S$ or retails, $s = S+1, ..., R$, available in stock in quantities $e_s, s = 1, ..., S+R$.

During the cutting process, usable leftovers (new retails) can be generated in limited quantities $U$ and with predefined sizes. This problem can have the objective of minimizing waste or any other objective function.

Several approaches have been proposed in the literature to solve CSPUL. The first ones focused on one-dimensional problems. A detailed discussion on 1D-CSPUL formulations can be found in Cherri et al. (2014). In all the proposed formulations and solution strategies, the usable leftovers were treated implicitly. Basically, the usable leftovers were considered as an undemanded item (Scheithauer, 1991), as any length greater than a certain threshold (Gradišar et al., 1997), as any length greater than the average length of the demanded item (Cherri et al., 2009), and other possibilities.

The first study to explicitly address and solve the usable leftovers in a mathematical model was proposed by Arenales et al. (2015). In this
approach, the possible leftovers were predefined in size and quantity. Since the stock available was composed of standard objects and for retails, according to the proposed model, new usable leftovers (retails) for the stock could only be generated from standard objects.

We present below the necessary notation of parameters and decision variables used in the formulation proposed by Arenales et al. (2015).

### Parameters

$J_s$ set of cutting patterns for object type $s, s = 1, ..., S + R$. No usable leftovers can be generated from these objects.

$J_s(k)$ set of cutting patterns for the standard objects of type $s$, that generate

$a_{ijs}$ a usable leftover type $S + k, k = 1, ..., R, s = 1, ..., S$. number of items type $i$ in cutting pattern $j$ for object type $s, i = 1, ..., m, s = 1, ..., S + R, j \in J_s$.

$a_{ijsk}$ number of items type $i$ in cutting pattern $j$ for object type $s$ and generating a usable leftover type

$c_{js}$ waste of cutting object/retail $s$ according to pattern $j, s = 1, ..., S + R, j \in J_s$.

$c_{jsk}$ waste of cutting object $s$ according to pattern $j$ when generating a leftover type

$$S + k, s = 1, ..., S, k = 1, ..., R, j \in J_s(k).$$

### Variables

$x_{js}$ number of object types $s$ cut according to pattern $j, s = 1, ..., S + R, j \in J_s$.

$x_{jsk}$ number of object types $s$ cut according to pattern $j$ generating a leftover type

$$S + k, s = 1, ..., S, k = 1, ..., R, j \in J_s(k).$$

The mixed-integer linear programming (MILP) formulation of this 1D-CSPUL is as follows:

$$ \text{Min } f(x) = \sum_{s=1}^{S} \sum_{j \in J_s} c_{js}x_{js} + \alpha' \sum_{s=1}^{S} \sum_{k=1}^{R} \sum_{j \in J_s(k)} c_{jsk}x_{jsk} + \alpha'' \sum_{s=S+1}^{S+R} \sum_{j \in J_s} c_{js}x_{js} \quad (1) $$

s.t.

$$ \sum_{s=1}^{S} \sum_{j \in J_s} a_{ijs}x_{js} + \sum_{s=1}^{S} \sum_{k=1}^{R} \sum_{j \in J_s(k)} a_{ijsk}x_{jsk} + \sum_{s=S+1}^{S+R} \sum_{j \in J_s} a_{ijs}x_{js} = d_i, \quad \forall i = 1, ..., m \quad (2) $$

$$ \sum_{j \in J_j} x_{js} + \sum_{k=1}^{R} \sum_{j \in J_s(k)} x_{jsk} \leq e_s, \quad \forall s = 1, \dots, S \quad (3) $$

$$ \sum_{j \in J_j} x_{js} \leq e_s, \quad \forall s = S + 1, \dots, S + R \quad (4) $$

$$ \sum_{s=1}^{S} \sum_{k=1}^{R} \sum_{j \in J_s(k)} x_{jsk} - \sum_{s=S+1}^{S+R} \sum_{j \in J_s} x_{js} \leq U - \sum_{s=S+1}^{S+R} e_s, \quad (5) $$

$$ x_{js} \geq 0, \quad \forall s = 1, \dots, S + R, \ j \in J_s \text{ and integer} \quad (6) $$

$$ x_{jsk} \geq 0, \quad \forall k = 1, \dots, R, \ s = 1, \dots, S, \ j \in J_s(k) \text{ and integer} \quad (7) $$

The objective function (1) minimizes the waste of cutting standard objects and retails of the stock. The parameters $a^t$ and $a^o$ indicate respectively, the incentive to generate usable leftovers or the use of retails from the stock. Constraints (2), (3), and (4) are responsible for ensuring that demand is met and that stocks of standard and retails are maintained, respectively. The quantity of usable leftovers generated for future use is limited by Constraint (5). Constraints (6) and (7) are non-negativity and integrality constraints.

Although formulation (1)–(7) represents the CSPUL, because of the exponential number of variables, constraints (6) and (7) were relaxed in Arenales et al. (2015) and the column generation method (Gilmore & Gomory, 1961) was used to find optimal solutions. As this work was the first in the literature to explicitly address usable leftovers in the mathematical model, it served as the basis for other research. All these works are reviewed in this paper.

## 2.2. 2D-CSPUL formulation

To the best of our knowledge, the first paper addressing the 2D-CSPUL was presented by Andrade et al. (2014). This problem shares a similar description with the one-dimensional case, with the key difference being that the items and objects are rectangular, defined by their dimensions (height and length). The two-dimensional nature of the problem introduces additional geometrical complexities. One significant challenge lies in managing the usable leftovers generated from the rectangular object. Unlike in the one-dimensional case, these leftovers can be oriented and positioned in multiple ways on the object, further complicating the problem.

In the 2D problems, the cuts are type *guillotine* and *non-guillotine*. A guillotine cut is an edge-to-edge cut in an object, perpendicular to the edge. In non-guillotine cuts, such a process is not mandatory, and there are no constraints on the positioning of items inside the object as long as space constraints are respected. Fig. 2 illustrates these types of cuts.

In the context of CSPUL, one approach involves the application of guillotine cuts to extract leftovers. This notion, known as guillotine leftovers, was introduced by Andrade et al. (2014). Two different approaches to generating usable leftovers were considered. The non-guillotine cutting patterns could have both guillotine and non-guillotine types of leftovers. To explore the possibility of obtaining guillotine leftovers in non-guillotine cutting patterns, the authors assumed that two guillotine leftovers could be generated from the object. In addition, each leftover was generated by only a single guillotine cut from an object. The two possibilities are shown in Fig. 3.

For the non-guillotine cutting problem with guillotine leftovers, the problem was formulated as a bilevel programming problem. In a bilevel formulation, an *upper level problem* includes a constraint requiring that a subset of the variables must be a solution of another optimization problem called the *lower level problem* (Dempe, 2002). The *lower level problem*, which is the constraint, was defined with the objective of minimizing the amount of material utilized in the cutting area. The *upper level problem* consists of maximizing the values of the vertical and horizontal leftovers.

Let us take $o \in O = \{1, ..., m\}$ as the set of objects, while $i \in I = \{1, ..., n\}$ represents the set of items. Also, let $(x_i, y_i)$ be the Cartesian center's coordinates of item $i$ assuming the left-bottom corner of the object is located at the origin of the two-dimensional plane. The notation of the mathematical programming formulation for the bilevel problem is given.

### Parameters

$W_o$ Width of object $o \in O$

$H_o$ Height of object $o \in O$

$p_o$ Price per unit area in object $o \in O$

$w_i$ Width of item $i \in I$

$h_i$ Height of item $i \in I$

### Variables

$u_o$ Binary variable equal to 1 if object $o \in O$ is used to cut at least one demanded item; 0 otherwise

$v_{io}$ Binary variable equal to 1 if item $i \in I$ is assigned to object $o \in O$; 0 otherwise

$r_o$ Width of the right-hand side leftover in object $o \in O$

$t_o$ Height of the top leftover in object $o \in O$

$a_o^t$ Area of the top leftover in Fig. 3(a) in object $o \in O$

$a_o^r$ Area of the right-hand side leftover in Fig. 3(a) in object $o \in O$

$\beta_o^t$ Area of the top leftover in Fig. 3(b) in object $o \in O$

$\beta_o^r$ Area of the right-hand side leftover in Fig. 3(b) in object $o \in O$

$x_i, y_i$ Cartesian center coordinates of item $i$

The bilevel problem is formulated as follows:

$$ \text{Max} \sum_{o=1}^{m} p_o \max\{a_o^t + a_o^r, \beta_o^t + \beta_o^r\} \quad (8) $$
<figure><img src="image_5.png" /><figcaption>Fig. 2. Examples of patterns with non-guillotine (a) and guillotine (b) cuts.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 3. Illustration of pre-cuts generated before starting the process of cutting the object. In (a), a vertical pre-cut is made first. In (b), a horizontal pre-cut is first generated (Andrade et al., 2014).</figcaption></figure>

$$ \alpha_o' = \begin{cases} (W_o - r_o)t_o, & \text{if there exists } 1 \le s \le d \text{ s.t. } W_o - r_o \ge \bar{w}_s \\ 0, & \text{otherwise} \end{cases} \quad \forall o \in O \quad (9) $$

$$ \alpha_o'' = \begin{cases} r_o H_o, & \text{if there exists } 1 \le s \le d \text{ s.t. } r_o \ge \bar{w}_s \\ 0, & \text{otherwise} \end{cases} \quad \forall o \in O \quad (10) $$

$$ \beta_o' = \begin{cases} W_o t_o, & \text{if there exists } 1 \le s \le d \text{ s.t. } W_o \ge \bar{w}_s \\ 0, & \text{otherwise} \end{cases} \quad \forall o \in O \quad (11) $$

$$ \beta_o'' = \begin{cases} r_o(H_o - t_o), & \text{if there exists } 1 \le s \le d \text{ s.t. } r_o \ge \bar{w}_s \\ 0, & \text{otherwise} \end{cases} \quad \forall o \in O \quad (12) $$

$$ u_i, v_{io}, x_i, y_i \in \argmin \sum_{o=1}^{m} \rho_o W_o H_o u_o \quad (13) $$

$$ u_o \ge v_{io}, \quad \forall i \in I, o \in O \quad (14) $$

$$ \sum_{o=1}^{m} v_{io} = 1, \quad \forall i \in I \quad (15) $$

$$ x_i - w_i/2 \ge 0, \quad \forall i \in I \quad (16) $$

$$ y_i - h_i/2 \ge 0, \quad \forall i \in I \quad (17) $$

$$ x_i + w_i/2 \le W_o - r_o + (\hat{W} - W_o)(1 - v_{io}), \quad \forall i \in I, o \in O \quad (18) $$

$$ y_i + h_i/2 \le H_o - t_o + (\hat{H} - H_o)(1 - v_{io}), \quad \forall i \in I, o \in O \quad (19) $$

$$ 0 \le t_o \le H_o u_o, \quad 0 \le r_o \le W_o u_o, \quad \forall i \in I, o \in O \quad (20) $$

$$ v_{io} = 1 \implies (x_i, y_i) \in [w_i/2, W_o - w_i/2] \times [h_i/2, H_o - h_i/2], \quad \forall i \in I, o \in O \quad (21) $$

$$ \begin{aligned} v_{io} = v_{i'o} = 1 &\implies |x_i - x_{i'}| \ge (w_i + w_{i'})/2 \text{ or} \\ |y_i - y_{i'}| &\ge (h_i + h_{i'})/2, \end{aligned} \quad \forall i, i' \in I, o \in O \quad (22) $$

$$ u_i \in \{0, 1\}, \quad \forall i \in I \quad (23) $$

$$ v_{io} \in \{0, 1\}, \quad \forall i \in I, o \in O \quad (24) $$

$$ x_i, y_i \ge 0, \quad \forall i \in I \quad (25) $$

The bilevel programming model consists of the maximization of the leftover's value (13), It is maximized through the best of cases (a) and (b) in Fig. 3. The total area is either $\alpha_o'$ or $\beta_o'$ or $\beta_o''$ or $\alpha_o''$, $\alpha_o''$, $\beta_o'$ and $\beta_o''$. In these constraints, $\bar{w}_s$ and $\bar{h}_s$ represent, respectively, the minimum width and height of the item. The upper level problem is subject to constraints (9)–(12) and to $u_i$, $v_{io}$, $x_i$, and $y_i$ as being a solution to the lower level problem represented by (13)–(24). Function (13) in this lower level problem aims to minimize the total cost of material usage. Constraints (14) ensure that an object is included in the cost function if at least one item is cut from it. Constraints (15) ensure that each item is assigned to exactly one object. If $v_{io} = 1$, Constraints (16)–(19) insure that item $i$ is contained within object $o$. In these constraints, $\hat{W} = \max_{o'=1,...,m}\{W_{o'}\}$ and $\hat{H} = \max_{o'=1,...,m}\{H_{o'}\}$. Constraints (20) guarantee that the height of the top leftovers and the width of the right-hand side leftovers are nonnegative and that they are zero if the object is not used. Constraints (21) and (22) force the item to be within the cutting area and avoid an overlap between items, respectively. Constraints (23) and (24) refer to the variables' definition.
### 3. Classification of problem variants and their formulations

This section classifies the studies based on four main criteria: The modeling of the problem using a pattern- or item-oriented approach, type of objective, time horizon (single or multiple periods), and type of cut (guillotine, non-guillotine, etc.). Other particular features are discussed in Section 6.

#### 3.1. Pattern-oriented vs. Item-oriented models

There are two main categories of cutting stock models: item-oriented and pattern-oriented models (Dyckhoff, 1990). Item-oriented models individually consider each item to be cut. In pattern-oriented models, items are grouped into feasible patterns, and the models determine how often each pattern should be cut to satisfy the demand. The integer linear programming (ILP) formulation proposed by Gilmore and Gomory (1961) was a pattern-oriented formulation. As described by Gradišar et al. (1997), a pattern-oriented approach is more adequate if the objects in stock have the same or several standard lengths. Another situation that imposes the use of item-oriented models is when the demand for some items is very low (see for example Abuabara and Morabito 2009).

In 1D-CSPUL, many formulations are based on mathematical programming models. In addition, for these problems, the position of each item on the object does not affect the quantity of leftovers. Therefore, the literature related to 1D-CSPUL is dominated by pattern-oriented models (25 papers), as indicated in Table 1. Regarding the item-oriented models, only nine papers have been published. The mathematical formulation in the paper from Arenales et al. (2015) presented in Section 2 is a pattern-oriented model. In this model, the variables $x_{js}$ and $x_{jsk}$ determine the cut frequency of the cutting patterns.

Pattern-oriented models also dominate 2D-CSPUL literature. It is usually more challenging to justify their use, as the number of object types can be very large and there are few items of identical size (Andrade et al., 2016). The formulation proposed by Andrade et al. (2014), presented in Section 2 is an item-oriented model with non-guillotine cuts. Note that there is no variable to indicate the frequency of the cutting pattern in the formulation.

For 3D-CSPUL the studies proposed are focused on item-oriented models. This is justified by the high level of heterogeneity in the types of objects used and items to be cut. Table 1 shows the papers classified as pattern- or item-oriented.

#### 3.2. Objective functions

We observed a large variety of objective functions used in 1D-CSPUL models (Table 2). However, most papers focus on minimizing waste similarly to Arenales et al. (2015) who proposed a mathematical model to minimize the waste while taking into account the cut of standard objects and retails from the stock. This model was detailed in Section 2 of this literature review. Three papers that have the objective of maximizing the profit were also found. These papers were proposed by Coelho et al. (2017), Karelaiti et al. (2011), and Rothe et al. (2017). Maximization of the retails value was proposed by Andrade et al. (2016, 2014). The formulation presented by Andrade et al. (2014) is discussed in Section 2 above. Similar objectives were used by Birgin et al. (2020, 2023) but in a multi-period context.

Tomat and Gradišar (2017) minimized the waste and the difference between the usable leftovers produced and used. This way it is possible to control level of leftovers inventory and to maintain it on an appropriate level. Gradišar and Trkman (2005) and Abuabara and Morabito (2009) minimized the waste but limited the number of usable leftovers to one. do Nascimento et al. (2023) proposed a mathematical model to minimize the waste considering uncertainty in demand of items.

The papers that focus on cost minimization represented the cost as the overall cost of the objects required to execute the orders (Cui et al., 2017; Gracia et al., 2013; Silva et al., 2014), the cost of waste, cost

<table><caption>Table 1
Pattern- and item-oriented models.</caption><thead><tr><th>Modeling</th><th>Dimension</th><th>References</th></tr></thead><tbody><tr><td rowspan="2">Pattern-oriented</td><td rowspan="2">1D</td><td>Arbib et al. (2023), Arenales et al. (2015), Bertolini et al. (2024), Bressan et al. (2023), Cherri et al. (2009, 2013, 2023), Chu and Antonio (1999), Coelho et al. (2017), Cui et al. (2017), Cui and Yang (2010), do Nascimento et al. (2020), Garraffa et al. (2016), Gracia et al. (2013), Huo et al. (2009), Khan et al. (2020), Koch et al. (2009), Maher et al. (2019), Melhem et al. (2021), Morillo-Torres et al. (2021), Ravelo et al. (2020), Roodman (1986), Sallaume et al. (2008), Scheithauer (1991), Sinuany-Stern and Weiner (1994)</td></tr><tr><td>Andrade et al. (2016), Chen et al. (2015), Clautiaux et al. (2019), Huo et al. (2009), Karelaiti et al. (2011), Li et al. (2022), do Nascimento et al. (2022, 2023), Oliveira et al. (2016), Parreño and Alvarez-Valdes (2021), Roberts (1984), Silva et al. (2010, 2014), Sumeththapiwat et al. (2020)</td></tr><tr><td rowspan="3">Item-oriented</td><td rowspan="3">1D</td><td>Abuabara and Morabito (2009), Baykasoğlu and Özbel (2021), de Araujo-Machado et al. (2020), Gradišar et al. (2018, 1997), Gradišar and Trkman (2005), Tomat and Gradišar (2017), Trkman and Gradišar (2007), Yang et al. (2006)</td></tr><tr><td>Andrade et al. (2014), Birgin et al. (2020, 2023)</td></tr><tr><td>Rothe et al. (2017), Viegas et al. (2016)</td></tr></tbody></table>

of storage, and material handling (Koch et al., 2009), cost of cutting and storage operations (do Nascimento et al., 2020), and transportation costs (Baykasoğlu & Özbel, 2021). Other objectives included minimizing the number of objects or raw materials used (Bressan et al., 2023; de Araujo-Machado et al., 2020). Cherri et al. (2009) defined the objective of CSPUL as having little or no waste, no intermediate waste, and a reduced number of usable leftovers. Larger usable leftovers offer better usability potential.

Multi-objective optimization models were also proposed, although many of them were treated as mono-objective. Gradišar et al. (1997) discussed a problem where leftovers are dependent on the cutting sequence of items. They attempted to minimize the number of uncut order lengths and then the waste, defined as the trim loss smaller than a given bound. Gradišar et al. (2018) proposed a strategy to minimize the number of usable leftovers followed by the minimization of waste. In their paper in the steel industry, Maher et al. (2019) developed a model with the objective of minimizing waste, maximizing the usage of steel leftovers, and minimizing steel recycling. Sinuany-Stern and Weiner (1994) considered two objectives: minimizing the waste and maximizing the number of usable leftovers in the last bar(s). The strategy proposed by Oliveira et al. (2016), reduces the waste of raw materials and optimizes their purchase and consumption.

Garraffa et al. (2016) minimized the number of standard objects used and maximized the sum of the squared leftovers as a secondary objective. Both objectives were expressed as a single mathematical expression. Ravelo et al. (2020) proposed several heuristics to minimize the waste and final inventory of usable leftovers. Gradišar et al. (1997) used a lexicographic approach to solve the bi-criteria problem in the textile industry. The two criteria were the minimization of the uncut order lengths and the minimization of waste (total trim loss). Finally, the paper of de Araujo-Machado et al. (2020) did not present a multi-objective model, but rather analyzed separately three different objectives: Minimization of retails, minimization of raw material, and minimization of total length cut of the object.
<table><caption>**Table 2**
Objectives functions of CSPUL.</caption><thead><tr><th>Objective(s)</th><th>Dimension</th><th>References</th></tr></thead><tbody><tr><td colspan="3"><strong>Models with single objective</strong></td></tr><tr><td rowspan="2">Minimize waste</td><td>1D</td><td>Abuabara and Morabito (2009), Arenales et al. (2015), Bertolini et al. (2024), Cherri et al. (2009), Gradišar and Trkman (2005), Khan et al. (2020), Melhem et al. (2021), Morillo-Torres et al. (2021), Sallaume et al. (2008), Tomat and Gradišar (2017), Trkman and Gradišar (2007), Yang et al. (2006)</td></tr><tr><td>2D</td><td>Sumetthapiwat et al. (2020)</td></tr><tr><td rowspan="2">Minimize cost</td><td>1D</td><td>Baykasoğlu and Özbel (2021), Chen et al. (2015), Cherri et al. (2023), Chu and Antonio (1999), Cui et al. (2017), Cui and Yang (2010), do Nascimento et al. (2020), Gracia et al. (2013), Koch et al. (2009), Li et al. (2022), Scheithauer (1991)</td></tr><tr><td>2D</td><td>Silva et al. (2014)</td></tr><tr><td>Minimize raw material</td><td>1D</td><td>Arbib et al. (2023), Bressan et al. (2023), Huo et al. (2009)</td></tr><tr><td>Minimize area used</td><td>2D</td><td>Clautiaux et al. (2019), do Nascimento et al. (2022, 2023), Parreño and Alvarez-Valdes (2021)</td></tr><tr><td>Minimize leftovers</td><td>1D</td><td>Cherri et al. (2013)</td></tr><tr><td>Minimize number of cuts</td><td>2D</td><td>Silva et al. (2010)</td></tr><tr><td rowspan="3">Maximize profit</td><td>1D</td><td>Coelho et al. (2017)</td></tr><tr><td>2D</td><td>Karelahti et al. (2011)</td></tr><tr><td>3D</td><td>Rothe et al. (2017)</td></tr><tr><td>Maximize value of retails</td><td>2D</td><td>Andrade et al. (2016, 2014), Birgin et al. (2020, 2023)</td></tr><tr><td>Minimize growth of retail stock</td><td>3D</td><td>Viegas et al. (2016)</td></tr><tr><td rowspan="2">Multi-objective models</td><td>1D</td><td>de Araujo-Machado et al. (2020), Garraffa et al. (2016), Gradišar et al. (2018, 1997), Maher et al. (2019), Ravelo et al. (2020), Roodman (1986), Sinuany-Stern and Weiner (1994)</td></tr><tr><td>2D</td><td>Oliveira et al. (2016), Roberts (1984)</td></tr></tbody></table>

For 2D-CSPUL, papers from Clautiaux et al. (2019), Parreño and Alvarez-Valdes (2021), and do Nascimento et al. (2022) had as objective the minimization of the total area used. A profit maximization model was proposed by Karelahti et al. (2011). The profit is calculated as the difference between the sales price of the items and several other costs including those of raw materials, machines, and knife changes. In Silva et al. (2010), the main objective was to minimize the number of cuts. Additional objectives, such as the total length of cuts and waste minimization, were also explored.

When 3D problems are considered, the number of usable leftover types generated increases rapidly with the increase in the number of items. Therefore, the objective chosen by Viegas et al. (2016) was to minimize the growth of generated leftovers over time.

### 3.3. Single-period vs. multi-period models

Most of the publications concerning CSPUL focus on single-period models, which can be separated into two categories:

* *Pure single-period models* do not include time considerations in their mathematical formulation. In such cases, the CSPUL produces items by cutting them from the current stock, which contains both standard objects and retails.

* *Dynamic single-period models* iteratively solve multiple single-period problems, each with its own randomly generated demand. For example, Cherri et al. (2013) proposed a procedure considering leftovers from previous periods by successively generating future demands in a simulation framework.

<table><caption>**Table 3**
Temporal horizon in CSPUL.</caption><thead><tr><th>Period(s)</th><th>Dimension</th><th>References</th></tr></thead><tbody><tr><td rowspan="3">Pure single-period models</td><td>1D</td><td>(Arbib et al., 2023; Arenales et al., 2015; Bertolini et al., 2024; Bressan et al., 2023; Cherri et al., 2009; Chu & Antonio, 1999; Coelho et al., 2017; Cui & Yang, 2010; de Araujo-Machado et al., 2020; Garraffa et al., 2016; Gracia et al., 2013; Gradišar et al., 2018, 1997; Gradišar & Trkman, 2005; Khan et al., 2020; Koch et al., 2009; Maher et al., 2019; Melhem et al., 2021; Morillo-Torres et al., 2021; Roodman, 1986; Sallaume et al., 2008; Scheithauer, 1991; Sinuany-Stern & Weiner, 1994; Yang et al., 2006)</td></tr><tr><td>2D</td><td>Andrade et al. (2016, 2014), Chen et al. (2015), Clautiaux et al. (2019), Huo et al. (2009), Karelahti et al. (2011), do Nascimento et al. (2022), Oliveira et al. (2016), Parreño and Alvarez-Valdes (2021), Roberts (1984), Silva et al. (2010), Sumetthapiwat et al. (2020)</td></tr><tr><td>3D</td><td>Rothe et al. (2017)</td></tr><tr><td rowspan="2">Dynamic single period models</td><td>1D</td><td>Baykasoğlu and Özbel (2021), Cherri et al. (2013, 2023), Cui et al. (2017), Ravelo et al. (2020), Tomat and Gradišar (2017)</td></tr><tr><td>3D</td><td>Viegas et al. (2016)</td></tr><tr><td rowspan="2">Multi-period models</td><td>1D</td><td>Abuabara and Morabito (2009), do Nascimento et al. (2020), Huo et al. (2009), Trkman and Gradišar (2007)</td></tr><tr><td>2D</td><td>Birgin et al. (2020, 2023), Li et al. (2022), Silva et al. (2014)</td></tr></tbody></table>

Explicit multi-period models consider that items and demand are known in advance. In a multi-period problem, the production of items can be anticipated and stored for several periods before their actual delivery date. Abuabara and Morabito (2009) proposed a MILP formulation for a multi-period case and solved it using a commercial MILP solver. More comprehensive multi-period models include the integration of LSP and CSP, as in do Nascimento et al. (2020). Unlike (Abuabara & Morabito, 2009), the model of do Nascimento et al. (2020) considers inventory holding costs for both items and retails. In all cases, demand was assumed to be deterministic, except in Cherri et al. (2023) and do Nascimento et al. (2023), who proposed two-stage stochastic optimization models to solve a problem with demand uncertainty in the 1D-CSPUL and 2D-CSPUL, respectively. Uncertainty on defects in the production objects was presented in a study by Arbib et al. (2023). Table 3 classifies the publications based on the previous definitions.

Considering Table 3, among the multi-period models, Trkman and Gradišar (2007) highlighted the relevance of shifting from single- to multi-period problems and their consequences on the need for reintegrating retails from one period to another. For such problems, demand is systematically considered as dynamic (time-dependent), and production planning decisions are considered, such as timing of production, lot sizes, and overtime. The paper from do Nascimento et al. (2020) goes in this direction. It proposed an integrated dynamic cutting stock and lot-sizing problem (LSP) with usable leftovers. This allows for holding items and delivering them later to satisfy future demands. A specific feature of these models is the distinction between the holding costs of standard objects and those of retails, which also considers holding retails that will be cut in the future. Furthermore, this problem has an extra decision, which is the decision to bring forward the production of items or generate usable leftovers. In two different 2D-CSPUL studies, Birgin et al. (2023) and Silva et al. (2014) considered inventory holding and setup costs, respectively.
<table><caption>**Table 4**
Type of cuts in 2D-CSPUL and 3D-CSPUL papers.</caption><thead><tr><th rowspan="2">Type of cut</th><th rowspan="2">Dimension</th><th colspan="2">References</th></tr><tr><th>Pattern-Oriented Models</th><th>Item-Oriented Models</th></tr></thead><tbody><tr><td rowspan="2">Non-Guillotine</td><td>2D</td><td>Roberts (1984)</td><td>Andrade et al. (2014), Birgin et al. (2020, 2023), Rothe et al. (2017)</td></tr><tr><td>3D</td><td></td><td></td></tr><tr><td rowspan="2">Guillotine</td><td>2D</td><td>Andrade et al. (2016), Chen et al. (2015), Clautiaux et al. (2019), Huo et al. (2009), Karelaiti et al. (2011), Li et al. (2022), do Nascimento et al. (2022, 2023), Oliveira et al. (2016), Parreño and Alvarez-Valdes (2021), Silva et al. (2010, 2014), Sumeththapiwat et al. (2020)</td><td></td></tr><tr><td>3D</td><td></td><td>Viegas et al. (2016)</td></tr></tbody></table>

<figure><img src="image_7.png" /><figcaption>**Fig. 4.** Retails with oblique cuts.</figcaption></figure>

<table><caption>**Table 5**
Exact solution methods for the CSPUL.</caption><thead><tr><th>Solution methods</th><th>Dimension</th><th>References</th></tr></thead><tbody><tr><td rowspan="3">Mathematical programming solvers</td><td>1D</td><td>Abuabara and Morabito (2009), Arbib et al. (2023), Arenales et al. (2015), de Araujo-Machado et al. (2020), Garraffa et al. (2016), Khan et al. (2020), Koch et al. (2009), Melhem et al. (2021), Morillo-Torres et al. (2021), Sallaume et al. (2008), Sinuany-Stern and Weiner (1994), Trkman and Gradišar (2007)</td></tr><tr><td>2D</td><td>Andrade et al. (2016, 2014), Birgin et al. (2020), Karelaiti et al. (2011), do Nascimento et al. (2022), Parreño and Alvarez-Valdes (2021), Silva et al. (2010, 2014)</td></tr><tr><td>3D</td><td>Rothe et al. (2017)</td></tr></tbody></table>

### 3.4. Type of cuts

Table 4 summarizes the types of cuts used in each 2D-CSPUL or 3D-CSPUL paper. It also shows whether the model is pattern- or item-oriented. One remarkable observation is that all pattern-oriented 2D-CSPUL models use guillotine-cut approaches, whereas item-oriented models are mostly used for non-guillotine problems.

A special case for 1D formulations was approached by Garraffa et al. (2016) that discussed case studies in joinery and truss cutting. Some cuts are orthogonal to the main dimension, whereas others are oblique (45°). Owing to the oblique cuts, the retail size becomes dependent on the cutting sequence and direction, as illustrated in Fig. 4. The sequence of item cuts and their orientations can also increase the waste.

## 4. Solution methods

Solution methods used in the literature to solve the CSPUL can be broadly classified as exact (Section 4.1) or heuristic (Section 4.2). Heuristic methods are further classified into six categories: simple and local search heuristics, LP-based heuristics, ad hoc heuristics, heuristics based on subsets of items and patterns, metaheuristics, and heuristics based on column generation.

### 4.1. Exact methods

The CSPUL is NP-hard. Only small-size instances can be solved to optimality in a reasonable amount of time. Similar to classical CSP, mathematical programming solvers are capable of handling CSPUL instances of reasonable dimensions. Table 5 shows publications where these solvers been used to solve the CSPUL.

Only commercial MILP solvers were used to solve the proposed (linear) mathematical programming formulations. The most commonly

used solver is CPLEX, combined with the C/C++ language or modeling tools such as GAMS. The 1D-CSPUL and most of the 2D-CSPUL are modeled directly as a MILP (e.g., Abuabara and Morabito 2009, Silva et al. 2010). A few 2D-CSPUL models were first formulated as nonlinear models, that were linearized and solved with a MILP solver (e.g., do Nascimento et al. 2022). Because the branch-and-cut procedure in MILP solvers can provide heuristic solutions, some authors, such as Parreño and Alvarez-Valdes (2021) suggested using it as an exact method for small instances and as a good heuristic for large instances. Rothe et al. (2017) presented optimal solutions of their 3D-CSPUL obtained using a solver. Results for small instances were reported.

### 4.2. Heuristic methods

Due to the difficulty of solving CSPUL, most of the strategies proposed in the literature are heuristics. Heuristic procedures find solutions to complex optimization problems where it is impractical to find an exact optimal solution in a reasonable computational time. In a general way, heuristic solutions do not guarantee optimality, but some of them can guarantee a certain level of quality represented by a maximum gap from the optimum. Table 6 summarizes the relevant references.

#### (i) Constructive heuristics and local search

Constructive heuristics start from an empty or partial solution and step by step build feasible solutions to optimization problems. In a local search heuristic, a good solution is found by iteratively improving a candidate solution based on its local neighborhood.

Cherri et al. (2009) adapted well-known constructive cutting stock heuristics to solve 1D-CSPUL. In Cherri et al. (2013), these heuristics were adapted to the case where leftovers in stock are given priority
<table><caption>**Table 6**
Heuristic solution methods for the CSPUL.</caption><thead><tr><th>Solution methods</th><th>Dimension</th><th>Reference</th></tr></thead><tbody><tr><td rowspan="3">Simple heuristics<br>and local search</td><td>1D</td><td>Bressan et al. (2023), Cherri et al. (2009, 2013)</td></tr><tr><td>2D</td><td>Chen et al. (2015), do Nascimento et al. (2022)</td></tr><tr><td>3D</td><td>Viegas et al. (2016)</td></tr><tr><td rowspan="2">LP-based heuristics</td><td>1D</td><td>Cherri et al. (2009, 2023), Coelho et al. (2017), Cui et al. (2017), Cui and Yang (2010), do Nascimento et al. (2020), Khan et al. (2020), Sinuany-Stern and Weiner (1994)</td></tr><tr><td>2D</td><td>Birgin et al. (2023)</td></tr><tr><td rowspan="2">Ad hoc heuristics</td><td>1D</td><td>Chu and Antonio (1999), Gradišar et al. (2018, 1997), Huo et al. (2009), Tomat and Gradišar (2017)</td></tr><tr><td>2D</td><td>Huo et al. (2009), Li et al. (2022), Roberts (1984), Silva et al. (2014)</td></tr><tr><td>Subsets of items or patterns</td><td>1D</td><td>Garraffa et al. (2016), Gradišar and Trkman (2005), Sallaume et al. (2008)</td></tr><tr><td rowspan="2">Metaheuristics</td><td>1D</td><td>Baykasoğlu and Özbel (2021), Bertolini et al. (2024), Gracia et al. (2013), Ravelo et al. (2020), Yang et al. (2006)</td></tr><tr><td>2D</td><td>Oliveira et al. (2016)</td></tr><tr><td rowspan="2">Column generation based heuristics</td><td>1D</td><td>Scheithauer (1991)</td></tr><tr><td>2D</td><td>Clautiaux et al. (2019), Sumetthapiwat et al. (2020)</td></tr></tbody></table>

during the cutting process. Bressan et al. (2023) proposed two local search heuristics. The first selects an item and cuts it into two smaller items, using those that generate a smaller leftover bar. The second removes an item and tries to fill the rest of the bar with larger items and then with smaller items. do Nascimento et al. (2022) presented a new 2D-CSPUL model that includes strip and macro-items. They proposed an iterative heuristic to solve large problems in acceptable computational time. Chen et al. (2015) combined a recursive technique to generate normal segments consisting of homogeneous strips, and a beam search to obtain three-stage cutting patterns taking into account usable leftovers. The first-fit decreasing and best-fit decreasing heuristics were proposed by Viegas et al. (2016) for a 3D-CSPUL problem. They introduced a fitness function that improves the best-fit-decreasing approach. As a result, stock growth is significantly reduced (– 52%) while mean stock weight increases by 17%.

### (ii) LP-based heuristics

LP-based heuristics (Linear Programming-based heuristics) are approximation techniques for solving optimization problems. These heuristics provide high-quality feasible solutions and use linear programming relaxations to construct or improve feasible solutions to problems.

Many authors proposed heuristics based on the linear relaxation of the original CSPUL. They used residual heuristics or rounding procedures to find integer solutions from the continuous solution obtained from the linear relaxation of the mathematical model proposed to represent the CSPUL. The linear relaxation is usually solved using column generation approaches based on the procedure proposed by Gilmore and Gomory (1961). Once the optimal solution of the linear relaxation is obtained, rounding techniques are applied to obtain an integer solution for the CSPUL. Cherri et al. (2009) used column generation to solve the relaxed problem and then used several residual heuristics to find the solution for the CSPUL. For more details on residual heuristics for the 1D-CSP, we invite the reader to see Poldi and Arenales (2009).

Coelho et al. (2017) first used CPLEX solver to solve a linear relaxation of the model proposed to represent the CSPUL with selling of retails. Then two residual heuristics were used to find integer feasible solutions. Khan et al. (2020) also proposed a post-optimization procedure based on rounding. In Cui et al. (2017), column generation and dynamic programming were used to solve a linear relaxation of the original problem. This results in solutions where the optimal solution contains fractions of patterns. Therefore, the authors use a rounding heuristic to obtain integer solutions.

The relax-and-fix is another example of an LP-based heuristics used to solve the CSPUL. do Nascimento et al. (2020) solved the 1D-CSPUL in a two-phase approach. In the first phase, column generation is used to find the optimal solution of the LP relaxation of the problem. In the second phase, a relax-and-fix procedure is applied iteratively to obtain an integer feasible solution. This phase is applied only on a pre-selected set of patterns among those obtained in the first phase. Cui and Yang (2010) proposed an approach based on two procedures. Firstly, an LP procedure satisfies most of the items demands by rounding the variables in optimal solution of the LP relaxation. Then, a sequential heuristic satisfies the remaining part of the item demand. The LP procedure used is an extension of that of Scheithauer (1991). Sinuany-Stern and Weiner (1994) proposed an LP-based heuristic approach for large instances, decomposing the whole instances into smaller independent instances. Birgin et al. (2023) proposed a forward-looking approach for the multi-period non-guillotine 2D-CSPUL introduced in Birgin et al. (2020). Single-period sub-problems are solved sequentially using an LP solver. Unlike the myopic approach, the method considers the impact of the decisions made in future steps of the system.

### (iii) Ad hoc heuristics

Ad hoc heuristics are procedures used to find a solution to a particular problem without being based on a theory. In general, these heuristics are created using intuition or experience and do not guarantee optimal solutions.

Chu and Antonio (1999) proposed a heuristic algorithm based on dynamic programming approach. It solves 12 out of 20 small test instances to optimality, with an average gap of 0.19%. For larger instances, their algorithm improved the real-life solution by an average of 8%. Huo et al. (2009) proposed a *Mixed Heuristic Algorithm* that can handle both 1D and 2D problems. Tomat and Gradišar (2017) minimized waste and the difference between the amount of usable leftovers produced and used. The authors discussed a trade-off related to the threshold *t* used to consider usable leftovers. Low values of the threshold *t* result in large quantities of small usable leftovers, whereas too-high values of *t* result in large waste. The parameter *t* was optimized using an iterative heuristic. Gradišar et al. (1997) studied a 1D-CSPUL formulated as a bi-criteria multidimensional knapsack problem with side constraints. The authors proposed a sequential heuristic that solves a series of knapsack problems. This algorithm achieves near-optimal results on 200 instances with 50 rolls and 1000 orders. This work gave rise to the computer program COLA, which was later improved and generalized in the CUT algorithm (Gradišar et al., 1999). In Gradišar et al. (2018), the COLA application was developed for large-scale items that do not fill a single standard object. The authors proposed an S-CUT algorithm that splits a large-scale order into smaller suborders that are processed independently. The CPLEX solver was used to optimally solve small sub-orders and the LCUT application was used for larger order lengths. Finally, Li et al. (2022) proposed a Sequential Leftovers Utilization Correction (SLUC) algorithm which prioritizes the use of leftovers before satisfying the remaining demand by generating new patterns.

### (iv) Heuristics considering subsets of items and patterns

The algorithms in Sallaume et al. (2008) and Garraffa et al. (2016) were both based on the reduction of the potentially huge number of existing patterns, before using a MILP solver on a restricted set of
<table><caption>**Table 7**
Applications of CSPUL in industry.</caption><thead><tr><th>Dimension</th><th>Industry</th><th>Reference</th></tr></thead><tbody><tr><td rowspan="7">1D</td><td>Clothing</td><td>Gradišar et al. (1997)</td></tr><tr><td>Marble</td><td>Baykasoğlu and Özbel (2021)</td></tr><tr><td>Metal</td><td>Abuabara and Morabito (2009), Bertolini et al. (2024), Chu and Antonio (1999), de Araujo-Machado et al. (2020), Gracia et al. (2013), Morillo-Torres et al. (2021), Sinuany-Stern and Weiner (1994)</td></tr><tr><td>Paper</td><td>Khan et al. (2020)</td></tr><tr><td>Silicon steel coil</td><td>Li et al. (2022)</td></tr><tr><td>Wood</td><td>Koch et al. (2009)</td></tr><tr><td>2D</td><td>Furniture</td><td>Oliveira et al. (2016), Roberts (1984)</td></tr><tr><td></td><td>Glass</td><td>Parreño and Alvarez-Valdes (2021)</td></tr><tr><td></td><td>Metal</td><td>Karelahi et al. (2011), Li et al. (2022)</td></tr><tr><td></td><td>PCB</td><td>Sumeththapiwat et al. (2020)</td></tr><tr><td></td><td>Wood</td><td>Silva et al. (2010)</td></tr><tr><td>3D</td><td>Steel</td><td>Viegas et al. (2016)</td></tr></tbody></table>

patterns. Sallaume et al. (2008) first used simple heuristics to generate an upper bound of the optimal solution, which allows the extraction of a small fraction of the possible patterns.

In Gradišar and Trkman (2005), the solution obtained with the CUT algorithm was improved by running a branch-and-bound algorithm on a sub-problem defined by a subset of standard objects and items. The definition of the sub-problem was slightly different in the case of a surplus or a shortage of material.

### (v) Metaheuristics

A metaheuristic is an iterative process that guides and may modify the operations of subordinate heuristics to produce high-quality solutions (Sörensen & Glover, 2013). At each iteration, the procedure manipulates either a complete (or partial) single solution or else a collection of solutions. In Yang et al. (2006) the authors used a tabu search with a simple neighborhood structure which consists of moving an order from its original position to another position in the cutting sequence. Gracia et al. (2013) proposed a sequential algorithm that first generates a set of cutting patterns using a genetic algorithm. Then, the 1D-CSPUL with the previously generated patterns is solved with another genetic algorithm. Finally, four algorithms are used to improve the solutions obtained in the previous stage.

Ravelo et al. (2020) obtained an initial solution with a first fit heuristic. Then they compared two metaheuristics for a bi-objective problem: a Greedy Randomized Adaptive Search Procedure (GRASP) with four different movements from one solution to a new one, and an *evolutive based metaheuristic*. According to the authors, the evolution method performs better for single period instances while the GRASP performs better for multi-period instances. Baykasoğlu and Özbel (2021) proposed a *Stochastic Diffusion Search* approaches in the marble cutting industry. The problem considered has two original features: customers can be upgraded, i.e., proposed products of higher quality for the same price, and two blocks of marble can be cut together if they are of similar height.

For the 2D-CSPUL, Oliveira et al. (2016) implemented a hybrid GRASP and Tabu Search algorithm.

### (vi) Column generation-based heuristics

Column generation-based heuristics are generally used to solve large combinatorial optimization problems with an exponential number of variables. Roodman (1986) generated an initial (potentially infeasible) solution using an adaptation of the procedure in Gilmore and Gomory (1961). Then, feasibility was heuristically sought, and the solution was improved by modifying the patterns. Scheithauer (1991) proposed a mathematical model to solve the CSPUL and used the column generation technique to solve it. The author included possible extra lengths

in the demand for items with no order to satisfy. These lengths were treated as possible leftovers. Integer solutions were generated from the optimal relaxed solution using a rounding procedure that also included the leftovers. Clautiaux et al. (2019) proposed several variants of evolutionary and diving heuristics (Sadykov et al., 2019) based on a Dantzig-Wolfe reformulation solved by column generation. These heuristics work with non-proper cutting patterns, i.e., patterns that cannot participate in a feasible integer solution of the problem. Sumeththapiwat et al. (2020) also used the diving method to solve the problem. Column generation was used to solve the relaxed version of the original 2D-CSP with fixed-size of usable leftovers. The pricing problem is a two-stage knapsack problem. Two rounding procedures are proposed to retrieve feasible solutions: (i) a solver is used to find a combination of the generated cutting patterns; (ii) truncated branch-and-price algorithm: the decision variables with fractional optimal value are rounded down to an integer value. A residual problem is then defined with the remaining demands. This residual problem is solved again using column generation.

## 5. Applications in industry

The explicit consideration of leftovers in cutting decisions requires an update of the industrial processes, in particular the flow of materials and information between the different business units. Fig. 5 is a swim-lane diagram showing the forward and backward flows. It starts with a customer order and includes the flow of information (dashed lines) and the flow of materials (solid lines). The use of leftovers complicates the management of product flows between Planning and Scheduling and Shop Floor; the shop floor may need to send leftovers back to the warehouse, which should manage these new references, and the planning and scheduling department should check whether there are suitable leftovers to satisfy customer demand before deciding to order new standard objects from suppliers.

One difficulty that can be observed is that not all cutting software accept objects with non-standard dimensions as input. To make the most out of leftovers, a manufacturing company must have an efficient information system that provides an accurate overview of all objects that can be used as raw materials. In addition, the company must have a good forecast of the next production orders or at least a real knowledge of the usability potential of each type of leftover. Another difficulty is that some cutting machines can only process objects of standard size.

The CSPUL is observed in industrial applications such as cutting organic products (wood, leather, paper), metals (steel, copper, aluminum, titanium), composite fibers and materials, ceramics, etc. Despite the large variety of materials being processed, it can be seen that metal is the main field of application for CSPUL. This type of application requires special attention because some types of metal can deteriorate (e.g., oxidize) and must be used within a certain period of time. In short, real problems always have peculiarities that motivate the study of new solution techniques. Some applications of CSPUL are presented next. Part of the literature is naturally based on specific applications, or at least inspired by an industrial context. This section identifies and discusses the literature related to the real applications listed in Table 7.

### (i) One-dimensional applications

The main field of 1D-CSPUL application is in the cutting of metal bars and tubes. In Chu and Antonio (1999) and Gracia et al. (2013), the metal products resulting from the cutting process are the finished goods manufactured by the considered companies. In Chu and Antonio (1999), square, round, and triangular tubes are cut, while structural metal beams are cut by a local metalworking company in the case of Gracia et al. (2013). In Abuabara and Morabito (2009), the metallic tubes are used to manufacture agricultural light aircraft. In de Araujo-Machado et al. (2020), the aluminum profiles are intermediate components used in the production of doors and windows. Note that the instances from these real applications can be of different sizes
<figure><img src="image_8.png" /><figcaption>Fig. 5. Swim-lane diagram to show the cutting process using leftovers.</figcaption></figure>

compared to the literature. In many situations, tests with real data can be more challenging to solve than randomly generated data sets. Furthermore, many companies need the results in a few minutes. This is a classical situation that motivates the development of new procedures to solve the problems. In the study by Abuabara and Morabito (2009) the number of total requested items varied from 7 to 120, the maximum number of item types was 34, and the maximum number of object types was 16. The authors underlined the fact that these instances are relatively small compared to other industries. Nevertheless, these instances took between a few seconds and more than one hour to be solved.

Khan et al. (2020) developed a study in a paper mill, with the objective to reduce waste in a 1D-CSPUL. Also with the aim of reducing the waste, Gradišar et al. (1997) studied the 1D-CSPUL in the clothing industry. The pieces of clothing were regrouped into rectangular pattern shapes whose width was identical to the fabric roll width.

Koch et al. (2009) described the CSP for a company producing glued laminated timber. The standard size of objects was 24 m, and the customers' demands were varying between 3 and 12 m. Therefore, leftovers could be stored for further use. Finally, Baykasoğlu and Özbel (2021) proposed an application in the marble industry, with the selection of marble blocks and the cutting sequencing of the marble plane.

These examples show the large variety of industrial applications of the 1D-CSPUL. The first and fourth authors of this manuscript, through their professional activity and collaboration with several companies, are also aware of other unpublished applications in the fields of the transportation industry (aircraft, naval, automotive), furniture and carpentry, aluminum packaging for cans or aerosol products, textile and leather works, and electric and communication cables.

Note that there are several papers that have presented problems similar to the 1D-CSPUL but were not considered in this literature review. For example, in the cutting stock problem with skiving, introduced by Johnson et al. (1997), several standard objects are joined to form larger objects. Skiving can be seen as a means to optimize the use of

leftovers. Examples of CSP with skiving can be found in the paper and plastic film industry (Chen et al., 2019), steel industry (Tanir et al., 2019) and safety belt industry (Arbib et al., 2002).

### (ii) Two-dimensional applications

The preliminary paper of Roberts (1984) addressed a CSP arising in the manufacturing of furniture and more particularly worktops. The study considered rectangular and L-shaped worktops. The mathematical model proposed includes waste constraint that anticipates the quantity of raw material remaining after removing the worktops. In Oliveira et al. (2016), the target industry was the cluster of furniture enterprises in the Portuguese North Region. However, the authors did not get real-life data and generated instances instead. The ROADEF/EURO challenge (ROADEF/EURO, 2018) addressed the guillotine cutting stock problem in the glass industry. Parreño and Alvarez-Valdes (2021) proposed a three-stage method for this problem. Their objective function maximizes the width really used in the last bin, i.e., the leftover. In the steel industry, Karelaiti et al. (2011) studied a cutting stock problem where product coils are cut out from mother coils such that the first cut extends the full width of the mother coil, and the second cut is made parallel to a side of the mother coil. Sumetthapiwat et al. (2020) studied a cutting problem arising in a company manufacturing Printed Circuit Boards (PCB). Leftovers were considered to have fixed size corresponding to the board size. Li et al. (2022) showed that their SLUC algorithm was able to reduce the total cost in a silicon steel coil industry by almost 14%.

### (iii) Three-dimensional applications

Viegas et al. (2016) studied the daily cutting of tailored steel blocks ordered by customers. The demands must first be assigned to steel blocks in stock. Then, 3D cutting heuristics are applied. The objective was to minimize the costs related to the steel stock. Due to the cost of steel blocks, usable blocks are stored. A major concern is to avoid stock growth.
# 6. Discussion

The CSPUL is part of everyday practice on many production lines and has been the focus of several researchers in searching for efficient solutions methods. The inclusion of usable leftovers in the optimization of cutting has made industrial processes more complex (see Fig. 5).

The literature raises many practical questions related to retail management, which involve distinguishing a retail from a waste, the value of the retail, and the management of a retail, among other difficulties. In addition to the models proposed in the literature that attempt to find trade-offs between the value of generating and storing retails and their incurred costs, it is important to discuss how these values and costs are estimated.

## 6.1. Definition of retails

A leftover is usually considered retail if it is sufficiently large to cut items from future demands. A recurring question in the literature is to define the criteria for determining whether a leftover is sufficiently large. The simpler criterion for the 1D-CSPUL is to define a threshold value. Generally, the threshold value is specific to each industry. In the literature, this value has already been considered as the size of the smallest item produced by a company (Gradišar & Trkman, 2005) or a value based on the smallest lengths of the upcoming production orders (Melhem et al., 2021). (Cherri et al., 2009) pointed out that thresholds based on the size of the smallest item may be unsatisfactory if it has an atypical shape or is produced infrequently.

The threshold can also be equal to the longest demanded item (Gradišar et al., 1997), or a fixed value corresponding to a standard size or machine setup. Tomat and Gradišar (2017) proposed a heuristic algorithm that dynamically determined the threshold value according to the stock level and storage capacity. The management of leftover thresholds in the 2D-CSPUL is considerably more complex because both dimensions, length and width, must be considered. The difficulty only increases for 3D problems.

Although several studies and conditions have already been discussed in the literature to determine whether a leftover is considered usable, this is always a challenge for both researchers and practitioners. In fact, the leftovers must be generated in specific situations with the main objective of contributing to the reduction of waste. The expectation is that these leftovers will be well used in the future, i.e., used in a way that generates very little or no waste. This is the main point of the discussion. For a leftover to be well used in the future, its size should be determined from the information about future demands, which is generally not fully available at the moment when the leftovers need to be determined. Cherri et al. (2023) used stochastic programming to determine the best size of the leftovers, taking into account possible future demand scenarios.

Some conditions and studies considered in the literature for the leftovers are presented next.

(i) **Larger than some items.** In many studies for 1D-CSPUL, the threshold for the leftover is often the size of the largest demanded item. Looking at 2D problems leftovers will be usable if they are sufficiently large in both dimensions. In these problems, it is not possible to consider only the area of the object because unusable leftovers may be generated (e.g., leftovers too long and too thin). Silva et al. (2010) considered a leftover to be usable if its length and width were greater than some of the items to be produced. Andrade et al. (2016) considered a threshold, defined as the smallest height of a demanded item.

(ii) **Pre-cut leftovers.** Pre-cutting usable leftovers has been adopted in several studies. This was the case in Andrade et al. (2014), Birgin et al. (2020, 2023), in which two usable leftovers were obtained through guillotine pre-cuts before starting the process of cutting items in the remaining area of the object (see Fig. 3).

(iii) **Dimensions of the smallest item.** Sumetthapiwat et al. (2020) considered all retails to have the same dimensions as the item type with the smallest height. This policy avoids creating more waste when using retails and also generates fewer retail sizes. Therefore, it is more suitable for solving large instances within an acceptable computing time.

(iv) **Predefined size.** Arenales et al. (2015), Scheithauer (1991), Coelho et al. (2017), and do Nascimento et al. (2020) considered retails with predefined length. This policy helps create what we call “standard retails” that are easier to manage and being more useful in the industrial case.

Based on the standard object. do Nascimento et al. (2022) proposed an approach where the leftovers must have the same length as the object and the height varies according to a percentage of this measure.

## 6.2. Value and costs associated with retails

Some mathematical models assign a monetary value to retails. However, it is difficult to estimate retail value accurately. The simplest case is when retails are cut to the dimensions of standard objects, in this case, they are assigned the value of the standard object. However, this valuation principle is questionable. When the retail stock is too large, it becomes complicated to identify the best retail to cut and extract from such stocks of non-standard objects. Consequently, valuing retails as a decreasing function of stock quantity seems to be a more realistic approach, but it would make mathematical models much more complex. By avoiding the proliferation of retails through different mechanisms, the approaches described in the literature avoid this complexity. The effect is to confine the retail quantity to a range in which their value is considered constant.

Creating and managing retails raise several types of specific costs. Firstly, there are additional cutting costs for retail cut to the size of standard objects. Then, there are the costs associated with handling operations and creating retail requires generating it in the information system, especially for retail with dimensions that have never been created before. All retails of the same material and size are considered as single product references if they have a limited number of predetermined fixed sizes (Arenales et al., 2015; Cui et al., 2017). In this case, they can be registered in the information system as already known references, simplifying the inventory policy. These costs are difficult to estimate. Therefore, they are rarely included in the optimization models.

Like any stored product, retails are subject to holding costs that depend on their value and the period for which they are stored. As mentioned in Section 3.3, most multi-period models explicitly include retail holding costs. In single-period models, retail holding costs are not included because the holding period is unknown.

## 6.3. Managing the number of retails

One of the main risks identified in the CSPUL is the proliferation of leftovers. To avoid this risk, it may be necessary to consider limiting the number of retails stored or prioritizing the use of retails over the use of new standard objects. In Cherri et al. (2013), the use of retails was prioritized over the unnecessary use of new bars. This policy is an effective means of limiting the stock of retails and avoiding excessive handling. Chu and Antonio (1999) used the penalty associated with leftovers to discourage their proliferation.

It is possible to produce several retails from a single cut if these retails have a high use value. However, a general strategy is to generate as few retails as possible because fewer retails means less cutting effort and material handling. It also means larger retails with a higher usability potential. An original approach was taken by Garraffa et al. (2016), who maximized the sum of the squared retails to favor solutions with fewer and larger retails.
# 7. Conclusions and future research

Based on this analysis, we conclude that the use of leftovers is gaining importance in operations research. The proposed mathematical formulations and solution methods were inspired by those used to solve the CSP (without leftovers).

Research on both the 1D-CSPUL and 2D-CSPUL (mostly guillotine cuts) remains active. Few papers have been published for 3D-CSPUL. The literature is dominated by pattern-oriented models with objective functions that minimize the cost or quantity of waste generated. Solution methods rely heavily on simple heuristics and the use of linear programming solvers (often combined with heuristics).

Several natural extensions of classical models have not yet been fully explored. To the best of our knowledge, the only studies introducing *uncertainty* are those of Cherri et al. (2023) on 1D-CSPUL and do Nascimento et al. (2023) on 2D-CSPUL, where future demand was stochastic, and Arbib et al. (2023) who consider uncertainty on defects in the objects. Considering the uncertainty of other parameters, such as the size of leftovers, yield and material availability, would also be relevant in the current context of an unstable market for raw materials. Only few multi-objective models exist. The objective functions used in the literature are often application dependent, therefore defining relevant objective functions remains a challenge.

The CSPUL has a positive impact on the triple bottom line of industrial companies. Also with the rising costs of raw materials and energy, the ability to use leftovers has a strong and direct *economic impact*.

The positive effects of the CSPUL are offset by the existence of indirect costs. Firstly, leftovers require handling resources to unload, store, and reload them onto the cutting machines. These handling operations can be more expensive than those for standard objects because they are less easily automated. Second, leftovers require storage capacity and can occupy different spaces if the inventory is organized by different sizes, shapes, etc. Finally, the cost of adapting or updating the information system and the ERP software should be considered. Therefore, studies of the various costs involved in moving from a CSP to a CSPUL model should be considered.

The *environmental impact* is also straightforward. However, quantifying this impact remains a challenge. Abuabara and Morabito (2009) reported that their CSPUL model generated 55% less waste than the CSP model used by the company. Further research is needed to provide a more thorough analysis of the environmental benefits of the CSPUL in terms of waste generated in addition to other upstream processes, such as raw material extraction, ecosystem damage, energy, chemical and water consumption, and greenhouse gas emissions.

The *social impact* has not yet received significant attention. Coelho et al. (2017) mentioned that the CSPUL will have a positive social impact, but there is no detailed discussion of this impact. We believe that the use of leftovers requires greater skills from operators. They need to have a broader view of a more complex production process with more diversified stocks.

In addition to operational research models and methods, the CSPUL offers a significant advantage in addressing the original industrial problems that give rise to the CSP. This approach enables a thorough examination and enhancement of operations management practices, such as inventory management, variety management of parts catalogs, and information system management.

There are other issues that require careful consideration. For example, the definition of leftovers is a critical aspect that needs to be addressed, and distinguishing between usable leftovers and waste is essential. Furthermore, determining the optimal amount of usable leftovers to maintain stock and effectively manage diversity is a significant challenge, and learning from past activities is another critical factor to consider.

Although the intrinsic value of leftovers remains constant, their likelihood of being used depends on several factors, such as the size, shape, presence of similar leftovers in stock, and anticipated manufacturing orders. An important question arises: what quantity and type of leftovers is beneficial to the company at any given time? Answering this question requires a comprehensive analysis of a company's past and present operations. There is a significant opportunity to combine optimization methods with learning techniques to determine the usability potential of leftovers. By examining historical data and evaluating current operations, optimization methods can be used to identify the optimal amount and specific types of leftovers that can be effectively used by a company. This integration of optimization and learning methods improves the decision-making process regarding the use of leftovers, maximizing their value.

Finally, leftovers have value, but there is still no market for them. Most studies have considered the internal use of leftovers. The leftovers stored for a given period can be used for further periods in the same production plant. A natural extension is to consider collaborative approaches consisting of models in which one company can buy leftovers from another company (Coelho et al., 2017). To optimize the distribution and sharing of cutting leftovers, it is essential to establish an efficient economic system specifically designed for this purpose. The first step is to develop marketplaces in which suppliers and potential users can connect. It is crucial to create incentives for cooperation within this economic system. This can be achieved by implementing appropriate pricing models, rewards for active participation, and transparent feedback systems. By providing tangible benefits and encouraging engagement, stakeholders will be motivated to actively participate in the distribution and sharing of cutting leftovers. Creating a well-designed economic system for the distribution and sharing of cutting leftovers can unlock their economic potential, reduce waste, and promote a more sustainable approach to materials management.

## CRediT authorship contribution statement

**Victor Senergues:** Writing – review & editing, Writing – original draft, Methodology, Formal analysis, Data curation, Conceptualization.
**Nadjib Brahimi:** Writing – review & editing, Writing – original draft, Validation, Supervision, Methodology, Formal analysis, Conceptualization.
**Adriana Cristina Cherri:** Writing – review & editing, Writing – original draft, Validation, Methodology.
**François Klein:** Writing – review & editing, Writing – original draft, Validation, Methodology, Formal analysis, Conceptualization.
**Olivier Péton:** Writing – review & editing, Writing – original draft, Validation, Supervision, Methodology, Formal analysis, Conceptualization.

## Acknowledgments

This work was supported by the French ANRT (Association Nationale de la Recherche et de la Technologie) through the PhD number 2021/0927 with CIFRE funds and a cooperation contract between REVERSE Systems and IMT Atlantique. Research of the third author was supported by Fundação de Amparo à Pesquisa do Estado de São Paulo - FAPESP, Brazil (Processes number 2022/05803-3 and 2024/05964-2), and the Conselho Nacional de Desenvolvimento Científico e Tecnológico - CNPq, Brazil (Processes number 317460/2021-8).

## References

* Abuabara, A., & Morabito, R. (2009). Cutting optimization of structural tubes to build agricultural light aircrafts. *Annals of Operations Research*, *169*, 149-165.

* Andrade, R., Birgin, E. G., & Morabito, R. (2016). Two-stage two-dimensional guillotine cutting stock problems with usable leftover. *International Transactions in Operational Research*, *23*(1-2), 121-145.

* Andrade, R., Birgin, E. G., Morabito, R., & Ronconi, D. P. (2014). MIP models for two-dimensional non-guillotine cutting problems with usable leftovers. *Journal of the Operational Research Society*, *65*(11), 1649-1663.
Arbib, C., Marinelli, F., Pferschy, U., & Ranjbar, F. K. (2023). One-dimensional stock cutting resilient against singular random defects. *Computers & Operations Research*, **157**.

Arbib, C., Marinelli, F., Rossi, F., & Di Iorio, F. (2002). Cutting and reuse: An application from automobile component manufacturing. *Operations Research*, **50**(6), 923-934.

Arenales, M. N., Cherri, A. C., do Nascimento, D. N., & Vianna, A. (2015). A new mathematical model for the cutting stock/leftover problem. *Pesquisa Operacional*, **35**, 509-522.

Baykasoğlu, A., & Özbel, B. K. (2021). Modeling and solving a real-world cutting stock problem in the marble industry via mathematical programming and stochastic diffusion search approaches. *Computers & Operations Research*, **128**, Article 105173.

Bertolini, M., Mezzogori, D., & Zammori, F. (2024). Hybrid heuristic for the one-dimensional cutting stock problem with usable leftovers and additional operating constraints. *International Journal of Industrial Engineering Computations*, **15**(1), 149-170.

Birgin, E. G., Romão, O. C., & Ronconi, D. P. (2020). The multiperiod two-dimensional non-guillotine cutting stock problem with usable leftovers. *International Transactions in Operational Research*, **27**(3), 1392-1418.

Birgin, E. G., Romão, O. C., & Ronconi, D. P. (2023). A forward-looking matheuristic approach for the multi-period two-dimensional non-guillotine cutting stock problem with usable leftovers. *Expert Systems with Applications*, **223**, Article 119866.

Bressan, G. M., Pimenta-Zanon, M. H., & Sakuray, F. (2023). A tree-based heuristic for the one-dimensional cutting stock problem optimization using leftovers. *Materials*, **16**(22).

Chen, Q., Chen, Y., Cui, Y., Lu, X., & Li, L. (2015). A heuristic for the 3-staged 2D cutting stock problem with usable leftover. In *2015 international conference on electrical, automation and mechanical engineering* (pp. 770-773). Atlantis Press.

Chen, Y., Song, X., Ouelhadj, D., & Cui, Y. (2019). A heuristic for the skiving and cutting stock problem in paper and plastic film industries. *International Transactions in Operational Research*, **26**(1), 157-179.

Cheng, C., Feiring, B., & Cheng, T. (1994). The cutting stock problem—a survey. *International Journal of Production Economics*, **36**(3), 291-305.

Cherri, A. C., Arenales, M. N., & Yanasse, H. H. (2009). The one-dimensional cutting stock problem with usable leftover-A heuristic approach. *European Journal of Operational Research*, **196**(3), 897-908.

Cherri, A. C., Arenales, M. N., & Yanasse, H. H. (2013). The usable leftover one-dimensional cutting stock problem—a priority-in-use heuristic. *International Transactions in Operational Research*, **20**(2), 189-199.

Cherri, A. C., Arenales, M. N., Yanasse, H. H., Poldi, K. C., & Vianna, A. C. G. (2014). The one-dimensional cutting stock problem with usable leftovers-A survey. *European Journal of Operational Research*, **236**(2), 395-402.

Cherri, A. C., Cherri, L. H., Oliveira, B. B., Oliveira, J. F., & Carravilla, M. A. (2023). A stochastic programming approach to the cutting stock problem with usable leftovers. *European Journal of Operational Research*, **308**(1), 38-53.

Chu, C., & Antonio, J. (1999). Approximation algorithms to solve real-life multicriteria cutting stock problems. *Operations Research*, **47**(4), 495-508.

Clautiaux, F., Sadykov, R., Vanderbeck, F., & Viaud, Q. (2019). Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers. *EURO Journal on Computational Optimization*, **7**(3), 265-297.

Coelho, K. R., Cherri, A. C., Baptista, E. C., Jabbour, C. J. C., & Soler, E. M. (2017). Sustainable operations: The cutting stock problem with usable leftovers from a sustainable perspective. *Journal of Cleaner Production*, **167**, 545-552.

Cui, Y., Song, X., Chen, Y., & Cui, Y.-P. (2017). New model and heuristic solution approach for one-dimensional cutting stock problem with usable leftovers. *Journal of the Operational Research Society*, **68**, 269-280.

Cui, Y., & Yang, Y. (2010). A heuristic for the one-dimensional cutting stock problem with usable leftover. *European Journal of Operational Research*, **204**(2), 245-250.

de Araujo-Machado, A., Zayatz, J. C., Melluzzi Neto, G., da Silva, M. M., Lapasini Leal, G. C., & Palma Lima, R. H. (2020). Aluminum bar cutting optimization for door and window manufacturing. *Dyna*, **87**(212), 155-162.

De Carvalho, J. V. (2002). LP models for bin packing and cutting stock problems. *European Journal of Operational Research*, **141**(2), 253-273.

Delorme, M., Iori, M., & Martello, S. (2016). Bin packing and cutting stock problems: Mathematical models and exact algorithms. *European Journal of Operational Research*, **255**(1), 1-20.

Dempe, S. (2002). *Foundations of bilevel programming*. Springer Science & Business Media.

do Nascimento, D. N., de Araujo, A., & Cristina, A. (2020). Integrated lot-sizing and one-dimensional cutting stock problem with usable leftovers. *Annals of Operations Research*, **1-19**.

Dyckhoff, H. (1990). A typology of cutting and packing problems. *European Journal of Operational Research*, **44**, 145-159.

Garey, M. R., & Johnson, D. S. (1979). *Computers and intractability: vol. 174*, freeman San Francisco.

Garraffa, M., Salassa, F., Vancroonenburg, W., Vanden Berghe, G., & Wauters, T. (2016). The one-dimensional cutting stock problem with sequence-dependent cut losses. *The one-dimensional cutting stock problem in Operational Research*, **23**(1-2), 5-24.

Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. *Operations Research*, **9**(6), 849-859.

Gracia, C., Andrés, C., & Gracia, L. (2013). A hybrid approach based on genetic algorithms to solve the problem of cutting structural beams in a metalwork company. *Journal of Heuristics*, **19**, 253-273.

Gradišar, M., Cesar, M., & Tomat, L. (2018). One-dimensional cutting stock optimisation by suborders. *Tehnički Vjesnik*, **25**(Supplement 2), 474-480.

Gradišar, M., Jesenko, J., & Resinovič, G. (1997). Optimization of roll cutting in clothing industry. *Computers & Operations Research*, **24**(10), 945-953.

Gradišar, M., Kljajić, M., Resinovič, G., & Jesenko, J. (1999). A sequential heuristic procedure for one-dimensional cutting. *European Journal of Operational Research*, **114**(3), 557-568.

Gradišar, M., & Trkman, P. (2005). A combined approach to the solution to the general one-dimensional cutting stock problem. *Computers & Operations Research*, **32**(7), 1793-1807.

Hadj Salem, K., Silva, E., & Oliveira, J. F. (2023). Cutting and packing problems under uncertainty: literature review and classification framework. *International Transactions in Operational Research*, **30**, 3329-3360.

Huo, Y., He, K., Zhang, R., & Zhong, Y. (2009). MHA: A mixed heuristic algorithm for the cutting stock problem. In *2009 international conference on information and automation* (pp. 460-465). IEEE.

Johnson, M. P., Rennick, C., & Zak, E. (1997). Skiving addition to the cutting stock problem in the paper industry. *SIAM Review*, **39**(3), 472-483.

Karelioti, J., Vainiomaki, P., & Westerlund, T. (2011). Large scale production planning in the stainless steel industry. *Industrial & Engineering Chemistry Research*, **50**(9), 4893-4906.

Khan, R., Pruncu, C. I., Khan, A. S., Naeem, K., Abas, M., Khalid, Q. S., & Aziz, A. (2020). A mathematical model for reduction of trim loss in cutting reels at a make-to-order paper mill. *Applied Sciences*, **10**(15), 5274.

Koch, S., König, S., & Wäscher, G. (2009). Integer linear programming for a cutting problem in the wood-processing industry: a case study. *International Transactions in Operational Research*, **16**(6), 715-726.

Le Hesran, C., Ladier, A.-L., Botta-Genoulaz, V., & Laforest, V. (2019). Operations scheduling for waste minimization: A review. *Journal of Cleaner Production*, **206**, 211-226.

Li, F., Chen, Y., & Hu, X. (2022). Manufacturing-oriented silicon steel coil lengthwise cutting stock problem with usable leftover. *Engineering Computations*, **39**(2), 477-492.

Lodi, A., Martello, S., & Monaci, M. (2002). Two-dimensional packing problems: A survey. *European Journal of Operational Research*, **141**(2), 241-252.

Maher, R. A., Melhem, N. N., & Almutlaq, M. (2019). Developing a control and management system for reinforcement steel-leftover in industrial factories. *IFAC-PapersOnLine*, **52**(13), 625-629.

Martello, S., Monaci, M., & Vigo, D. (2003). An exact approach to the strip-packing problem. *INFORMS Journal on Computing*, **15**(3), 310-319.

Melega, G. M., de Araujo, S. A., & Jans, R. (2018). Classification and literature review of integrated lot-sizing and cutting stock problems. *European Journal of Operational Research*, **271**(1), 1-19.

Melhem, N. N., Maher, R. A., & Sundermeier, M. (2021). Waste-based management of steel reinforcement cutting in construction projects. *Journal of Construction Engineering and Management*, **147**(7), Article 04021056.

Morillo-Torres, D., Baena, M. T., Escobar, J. W., Romero-Conrado, A. R., Coronado-Hernández, J. R., & Gatica, G. (2021). A mixed-integer linear programming model for the cutting problem in the steel industry. In *Applied computer sciences in engineering: 8th workshop on engineering applications*, WEA 2021, Medellín, Colombia, October 6-8, 2021, proceedings 8* (pp. 315-326). Springer.

do Nascimento, D. N., Cherri, A. C., & Oliveira, J. F. (2022). The two-dimensional cutting stock problem with usable leftovers: mathematical modelling and heuristic approaches. *Operational Research*, **22**(5), 5363-5403.

do Nascimento, D. N., Cherri, A. C., Oliveira, J. F., & Brito Oliveira, B. (2023). The two-dimensional cutting stock problem with usable leftovers and uncertainty in demand. *Computers & Industrial Engineering*, **186**, Article 109705.

Oliveira, O., Gamboa, D., & Fernandes, P. (2016). An information system for the furniture industry to optimize the cutting process and the waste generated. *Procedia Computer Science*, **100**, 711-716.

Parreño, F., & Alvarez-Valdes, R. (2021). Mathematical models for a cutting problem in the glass manufacturing industry. *Omega*, **103**, Article 102432.

Poldi, K. C., & Arenales, M. N. (2009). Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths. *Computers & Operations Research*, **36**(6), 2074-2081.

Ravelo, S. V., Meneses, C. N., & Santos, M. O. (2020). Meta-heuristics for the one-dimensional cutting stock problem with usable leftover. *Journal of Heuristics*, **26**, 585-618.

ROADEF/EURO (2018). ROADEF/EURO challenge: Cutting optimization problem. Available at https://www.roadef.org/challenge/2018/en/, 2023-06-23.

Roberts, S. (1984). Application of heuristic techniques to the cutting-stock problem for worktops. *Journal of the Operational Research Society*, **35**(5), 369-377.

Roodman, G. M. (1986). Near-optimal solutions to one-dimensional cutting stock problems. *Computers & Operations Research*, **13**(6), 713-719.

Rothe, M., Reyer, M., & Mathar, R. (2017). Process optimization for cutting steel-plates.. In *Proceedings of the 6th international conference on operations research and enterprise systems* (pp. 27-37).
Sadykov, R., Vanderbeck, F., Pessoa, A., Tahiri, I., & Uchoa, E. (2019). Primal heuristics for branch and price: The assets of diving methods. *INFORMS Journal on Computing, 31*(2), 251–267.

Sallaume, S., Mine, M. T., Silva, M. S., Ochi, L. S., & Plastino, A. (2008). One dimensional cutting stock problem with redevelopment of the surplus material. In *International conference on engineering optimization: vol. 6*.

Scheithauer, G. (1991). A note on handling residual lengths. *Optimization, 22*(3), 461–466.

Silva, E., Alvelos, F., & De Carvalho, J. V. (2010). An integer programming model for two-and three-stage two-dimensional cutting stock problems. *European Journal of Operational Research, 205*(3), 699–708.

Silva, E., Alvelos, F., & Valério de Carvalho, J. (2014). Integrating two-dimensional cutting stock and lot-sizing problems. *Journal of the Operational Research Society, 65*(1), 108–123.

Sinuany-Stern, Z., & Weiner, I. (1994). The one dimensional cutting stock problem using two objectives. *Journal of the Operational Research Society, 45*(2), 231–236.

Sörensen, K., & Glover, F. (2013). Metaheuristics. *Encyclopedia of Operations Research and Management Science, 62*, 960–970.

Sumetthapiwat, S., Intiyot, B., & Jeenanunta, C. (2020). A column generation on two-dimensional cutting stock problem with fixed-size usable leftover and multiple stock sizes. *International Journal of Logistics Systems and Management, 35*(2), 273–288.

Tanir, D., Ugurlu, O., Guler, A., & Nuriyev, U. (2019). One-dimensional cutting stock problem with divisible items: a case study in steel industry. *TWMS Journal of Applied and Engineering Mathematics, 9*(3), 473–484.

Tomat, L., & Gradišar, M. (2017). One-dimensional stock cutting: optimization of usable leftovers in consecutive orders. *Central European Journal of Operations Research, 25*(2), 473–489.

Trkman, P., & Gradišar, M. (2007). One-dimensional cutting stock optimization in consecutive time periods. *European Journal of Operational Research, 179*(2), 291–301.

Viegas, J. L., Vieira, S. M., Henriques, E. M., & Sousa, J. M. (2016). Heuristics for three-dimensional steel cutting with usable leftovers considering large time periods. *European Journal of Industrial Engineering, 10*(4), 431–454.

Yang, C.-T., Sung, T.-C., & Weng, W.-C. (2006). An improved tabu search approach with mixed objective function for one-dimensional cutting stock problems. *Advances in Engineering Software, 37*(8), 502–513.