1 Introduction

The one-dimensional cutting stock problem with setup cost (CSP-S) addresses a set of objects of length L and a set \(I = \{1,\ldots ,M\}\) of item types. Each item type \(i \in I\) has length \(l_i\) and demand \(d_i\). The objective is to minimize both the number of objects used to manufacture all the demanded items and the number of (different) patterns. It is known that the CSP-S is strongly NP-Hard (Garey and Johnson 1979; McDiarmid 1999). According to the typology of Wäscher et al. (2007) for Cutting and packing problems, the CSP-S is classified as a variant of the one-dimensional single stock size cutting stock problem (CSP), since it additionally considers how to reduce the number of patterns. A feasible solution to the CSP-S can be seen as a cutting plan, that is, a set of patterns and their frequencies, where:

  1. (i)

    a pattern is a M-dimensional non-negative integer vector \(x = (x_1, x_2, \ldots , x_M)^\top \), where \(x_i\) represents how many items of type \(i \in I\) are cut from a single object, that satisfies the inequality \(\sum _{i \in I} l_i x_i \le L\) (containment constraint);

  2. (ii)

    the frequency of a pattern represents the number of objects that has to be applied with the pattern;

  3. (iii)

    the demand of each item type \(i\in I\) should be fulfilled exactly or in excess.

Real applications of the CSP-S include the cutting of objects in the paper, steel, glass and plastic film industries to manufacture items. In this context, the production is stopped to set up the knives of the cutting machine for each new pattern (Haessler 1975). The stages of production following the cutting machine tend to be impacted as well. Thus, in addition to the main objective of minimum waste solutions, solutions with a minimum number of patterns are also desired. A typical solution to the problem usually has a small number of patterns with high frequencies. From a practical perspective, a satisfactory approach should tackle the bi-objective CSP-S to provide a set of solutions that find the best trade-off between the number of objects and the number of patterns (Umetani et al. 2003). This approach could be embedded into an expert system to assist decision-making, and it would avoid determining the setup cost explicitly.

1.1 Related work

The CSP-S is mainly addressed by heuristics, commonly based on pattern generation or meta-heuristics with local search (Henn and Wäscher 2013). The Sequential Heuristic Procedure (SHP) of Haessler (1975) was one of the first approaches for the CSP-S. A SHP is a greedy algorithm that seeks to generate a few patterns with high frequencies sequentially to satisfy the demands of some item types until complete exhaustion of the demand. It usually requires short processing times, and has parameters to guide the search in the trade-off between the number of objects and the number of patterns. Yanasse and Limeira (2006), Cui and Liu (2011), Mobasher and Ekici (2013), Cui et al. (2015) and Martin et al. (2018) proposed other SHP-based approaches for the CSP-S. These approaches differ mainly regarding how to generate feasible patterns, and the use of (post-)optimization techniques to reduce the number of patterns further. For instance, one could combine two patterns into a single new pattern heuristically, where the frequency of the new pattern is equal to the sum of the frequencies of the two previous patterns (Diegel et al. 1993). Foerster and Wäscher (2000) developed the KOMBI method by combining p patterns into new \(p-1\) patterns, where \(p \le 4\).

As for meta-heuristics algorithms, Umetani et al. (2003) developed an Iterated Local Search (ILS) algorithm for the CSP-S that searches for solutions with a constant number of p patterns. Constant p is varied in the algorithm to obtain the more advantageous solution within an adaptive pattern generation technique used in the local search. Later Umetani et al. (2006) further improved the previous work by proposing two types of local search based on the 1-add neighborhood and the shift neighborhood, and an auxiliary linear program to reduce the size of the neighborhood. Lee (2007) developed the Crawla algorithm for the bi-objective CSP-S which can be seen as a large large neighborhood search (Henn and Wäscher 2013). This iterative algorithm uses an integer linear programming (ILP) framework for generating and fixing new patterns in the solution. Golfeto et al. (2009) and Araujo et al. (2014) also developed meta-heuristics based on evolutionary algorithms with local search for the bi-objective CSP-S. More recently, Aliano Filho et al. (2018) presented an interesting study on four scalarization methods for the bi-objective CSP-S in which the patterns are given as input. They applied the weighted sum method, the classical Chebyshev metric, a novel modified Chebyshev metric and the \(\varepsilon \)-Constraint method. As for recent heuristic approaches for two-dimensional cutting problems with setup cost, we refer the reader to Ma et al. (2019) and Wang et al. (2020).

A problem related to the CSP-S is the Pattern Minimization Problem (PMP) that consists of minimizing the number of patterns subject to a limited number of objects. We are aware of three exact approaches that addressed the PMP by proposing branch-price-and-cut algorithms that fulfilled the demand of items without surplus (Vanderbeck 2000; Belov and Scheithauer 2003; Alves and Valério De Carvalho 2008). Vanderbeck (2000) proposed a master problem, where each column represents a feasible pattern associated with a possible frequency. His column generation procedure relied on solving a quadratic integer sub-problem that was copied by solving a set of bounded knapsacks for each possible value of frequency for each pattern. The author proposed superadditive functions to strengthen the model. Alves and Valério De Carvalho (2008) further improved the previous algorithm with the use of an upper bound on the number of maximum frequencies of a pattern and of dual feasible functions. To derive a robust branching scheme and stronger cuts, the authors also proposed an arc flow formulation with integer variables \(x_{rs}^n\) that represent the flow over arcs (r, s) (discrete positions within the object) in a pattern of frequency n. They also showed how the use of an upper bound on trim loss can reduce the maximum number of frequencies of a pattern. Belov and Scheithauer (2003) treated an extension of the Gilmore and Gomory (1961)’s model that was discussed in Vanderbeck (2000) as a master problem, which leads to fewer number of variables, however with weaker LP-bounds. The author seek to overcome this behavior with a branching scheme based on variables and enforcing branching constraints on single fractional variables. In a short, better results was obtained by the algorithm of Alves and Valério De Carvalho (2008) considering a set of 16 real-life instances. All these approaches had to tackle weaker lower bounds in the column generation procedure due to the structure of the PMP, which differs consistently from the tight bounds obtained by the approach of Gilmore and Gomory (1961) for the CSP. In this context, Alves et al. (2009) developed more tight lower bounds for the PMP which were obtained by solving a column generation framework. They strengthened these lower bounds with a constraint programming approach and valid inequalities.

Lastly, we note the ILP formulation of Johnston and Sadinlija (2004) for the CSP that can easily address the CSP-S. The authors proposed binary variables \(x_ {ijk}\) that are equal to 1, if k copies of item type i appear in the pattern j, and 0 otherwise. To our knowledge, this model has not been specifically assessed with computational experiments in the context of the bi-objective CSP-S.

1.2 Our contributions

In this paper, we propose a pattern-based pseudo-polynomial ILP formulation for the CSP-S. It relies on the development of an upper bound on the maximum frequency of each pattern in the cutting plan. The formulation is related to the master problem proposed in Vanderbeck (2000) in the sense that it considers a binary variable for each pair of a pattern and a possible frequency. Then, we incorporate it into a straightforward framework to solve the bi-objective CSP-S that minimizes the number of objects subject to a limited number of patterns. Since we are not aware of other exact approaches for the problem, we derive an ILP formulation based on Harjunkoski et al. (1996) into this framework to provide an alternative approach. We performed computational experiments with two well-known sets of benchmark instances from the literature to evaluate the advantages/disadvantages of the approaches. The results indicated that the proposed models using a general-purpose ILP solver are able to obtain Pareto (near-)optimal frontier for small and moderate-sized problem instances. They are appropriate for instances with solutions characterized by a moderate number of objects and a few patterns in the Pareto optimal frontier. We presume that these models can benefit OR practitioners interested in solving the CSP-S with a general-purpose ILP solver as a black box.

1.3 Organization of the paper

The rest of the paper is organized as follows. In Sect. 2, we describe the CSP-S with a bi-objective non-linear model. We discuss how to eliminate symmetries through an upper bound on the maximum frequency of each pattern in the cutting plan, as well as an upper bound on the number of items per type in a pattern. In Sect. 3, we introduce an ILP formulation for the CSP-S that is based on the non-linear model, which consists in modeling the frequency of each pattern as a binary expansion. Then, we propose a novel pseudo-polynomial ILP formulation for the CSP-S that considers each pair of a pattern and a possible frequency as a binary variable. In Sect. 4, we develop a straightforward framework that can use either of the two proposed models to solve the bi-objective CSP-S that minimizes the number of objects subject to a limited number of patterns. In Sect. 5, the performance of the proposed models derived from this framework is analyzed through computational experiments using two sets of benchmark instances from the literature. We also present a brief discussion of the ILP formulations of Johnston and Sadinlija (2004) and Alves and Valério De Carvalho (2008) with some additional results. Final remarks and perspectives of future research are discussed in Sect. 6.

2 A non-linear model for the CSP-S

The CSP-S is a cutting problem that seeks a cutting plan with a minimum number of objects used to manufacture all the demanded items and a minimum number of patterns. The problem arises in manufacturing settings with a limited capacity in the stage of cutting operations. That is the case of production systems that improve the productivity of the cutting machine (e.g. meters cut per hour) with fewer setups (i.e. cutting plans with fewer patterns) at the expense of increasing the trim loss. Thus, it is commonly assumed that the number of setups is equal to the number of different patterns. Note that limited capacity is not an issue for most of the cutting problems, like in the approach of Cerqueira et al. (2021) for the CSP, since they seek mainly solutions with minimum waste for input minimization problems or maximum profit for output maximization problems (Wäscher et al. 2007). However, these solutions could even not be feasible in the context mentioned above. We define the following parameters and sets to be used in the presentation of the models:

L

is the length of the objects;

\(I = \{1,\ldots ,M\}\)

is the set of item types;

\(l_i\) and \(d_i\)

are the length and demand of item type \(i \in I\), respectively; and

\(K = \{1,\ldots ,N\}\)

is the set of patterns.

We assume that \(l_i \le L\) and \(d_i\), \(i \in I\), are positive integers. Parameter N of the maximum number of patterns can be obtained by solving a heuristic for the CSP without considering the setup cost or by a previous definition of the decision-maker. We next formulate the CSP-S as a Bi-objective Integer Non-linear Programming model, inspired in a pattern-based approach (Kantorovich 1960; Scheithauer 2018). The formulation is given by Model (1), where the patterns are not given a priori.

$$\begin{aligned} \mathbf{Minimize}&\quad \sum _{k \in K} z_k.&\end{aligned}$$
(1a)
$$\begin{aligned} \mathbf{Minimize}&\quad \sum _{k \in K} y_k.&\end{aligned}$$
(1b)
$$\begin{aligned} \mathbf{subject} \,\mathbf{to}&\nonumber \\&\sum _{i \in I} l_i x_{ki} \le L y_k,&k \in K. \end{aligned}$$
(1c)
$$\begin{aligned}&\sum _{k \in K} z_k x_{ki} \ge d_i,&i \in I. \end{aligned}$$
(1d)
$$\begin{aligned}&z_k \le M^k y_k,&k \in K. \end{aligned}$$
(1e)
$$\begin{aligned}&x_{ki} \in {\mathbb {Z}}_+,&k \in K, i \in I. \end{aligned}$$
(1f)
$$\begin{aligned}&z_{k} \in {\mathbb {Z}}_+, \; y_{k} \in \{0,1\},&k \in K,\ \end{aligned}$$
(1g)

where

\(x_{ki}\)

is an integer variable that represents how many items of type \(i \in I\) are produced when

cutting one object with pattern \(k \in K\);

\(z_k\)

is an integer variable that represents the frequency of pattern \(k \in K\), i.e, the number of

objects that have to be cut with this pattern; and

\(y_k\)

is a binary variable that equals (1), if pattern \(k \in K\) is used, and (0) otherwise.

Objective function (1a) minimizes the number of objects, and objective function (1b) minimizes the number of patterns. These are conflicting objectives, since improving one usually is to the detriment of the other (Aliano Filho et al. 2018). Constraints (1c) ensure that the sum of the length \(l_i\) of the items does not exceed the length L of the object, for each pattern \(k \in K\). These constraints also enforce that \(x_{ki} = 0\) for each \(i \in I\), when \(y_k = 0\). Constraints (1d) ensure that the demand of each item type \(i \in I\) is fulfilled exactly or in excess. Constraints (1e) enforce that \(y_k=1\), when \(z_k > 0\) for each \(k \in K\). Constraints (1f) and (1g) define the domain of the variables. Model (1) is non-linear and non-convex due to the bilinear terms in the left-hand side of constraints (1d). In Sect. 3, we present equivalent mixed-integer linear models to this non-linear model, which allow employing general-purpose ILP solvers, such as CPLEX and GUROBI, to solve more practical problem instances of the CSP-S. Note that we can reformulate Model (1) as a mono-objective ILP formulation by replacing only objective functions (1a) and (1b) with the following objective function:

$$\begin{aligned} \mathbf{Minimize}&\quad c_o \sum _{k \in K} z_k + c_p \sum _{k \in K} y_k,&\end{aligned}$$

that minimizes the total cost of objects and patterns, where \(c_o\) and \(c_p\) are the coefficients that represent the unitary cost of a object and of a pattern, respectively.

2.1 Eliminating symmetries or equivalent solutions

The pattern-based formulations for the CSP and its variants present the disadvantage of the symmetries on the patterns, that is, the interchangeability of indices \(k \in K\), which may lead to difficulties in a branch-and-bound procedure (Vanderbeck 2000). One strategy to partially circumvent the disadvantage is to introduce the valid inequalities \(z_k \ge z_{k+1}\), \(k \in K\backslash \{N\}\). These valid inequalities ensure that the patterns in the cutting plan are sorted in a non-increasing order of the frequencies of the patterns (Johnston and Sadinlija 2004). To attenuate other equivalent solutions, we define the following parameters to focus on the domain of variables \(z_k\) and \(x_{ki}\) next:

\({\overline{z}}\)

is the upper bound on the number of objects in the solution;

\({\underline{y}}\)

is the lower bound on the number of patterns in the solution;

\(d_{max}=\displaystyle \max _{i \in I} \{d_i\}\)

is the maximum demand of the item types;

\(M^k\)

is the upper bound on the frequency of pattern \(k \in K\); and

\(O^i\)

is the upper bound on the number of items of type \(i \in I\) in any pattern.

In Theorem 1 we state an upper bound on each variable \(z_k\), \(k \in K\).

Theorem 1

An upper bound on each variable \(z_k\), \(k \in K\), in the cutting plan is given by \(M^k = \min \{{\lfloor }({\overline{z}}-\max \{0,{\underline{y}}-k\})/k{\rfloor },d_{max}\}\).

Proof

We assume that valid inequalities \(z_k \ge z_{k+1}\), \(k \in K\backslash \{N\}\), hold. It is easy to see that \(z_1 \le \min \{{\overline{z}},d_{max}\}\), since the frequency of a pattern in an optimal solution cannot be greater than the total number of objects in the solution, nor the maximum demand of any item type. Recall that \(z_1 \ge z_2\) and \(z_1 + z_2 \le {\overline{z}}\). Therefore, \(z_2 + z_2 \le z_1 + z_2 \le {\overline{z}}\). Then \(2 z_2 \le {\overline{z}}\), and so \(z_2 \le {\lfloor }{\overline{z}}/2{\rfloor }\). More precisely, \(z_2 \le \min \{{\lfloor }{\overline{z}}/2{\rfloor },d_{max}\}\). Using a similar reasoning by induction, we can derive \(z_3 \le \min \{{\lfloor }{\overline{z}}/3{\rfloor },d_{max}\}\). In a general form, \(z_k \le \min \{{\lfloor }{\overline{z}}/k{\rfloor },d_{max}\}\) for each \(k \in K\). Considering that any solution has at least \({\underline{y}}\) patterns, then \(z_k \le \min \{{\lfloor }({\overline{z}}-\max \{0,{\underline{y}}-k\})/k{\rfloor },d_{max}\}\) for each \(k \in K\). \(\square \)

An upper bound on each variable \(x_{ki}\), \(k \in K\) and \(i \in I\), is given by \(O^i = \min \{{\lfloor }L/l_i{\rfloor },d_i\}\). Alternatively stated, it is the minimum value between the geometric bound \({{\lfloor }L/l_i{\rfloor }}\) and the demand \(d_i\) of item type \(i \in I\) (Nitsche et al. 1999).

3 Two pattern-based ILP formulations for the CSP-S

In this section, we introduce two pattern-based ILP formulations for the CSP-S. The first is based on the non-linear model of the previous section, and it consists of representing variables \(z_k\) as a binary expansion. The second is a novel pseudo-polynomial formulation that considers each possible combination of pattern and frequency as a binary variable. These two formulations make use of the upper bounds discussed in the previous section, especially upper bound \(M^k\) on the frequency of each pattern \(k \in K\), since it determines their number of variables and constraints.

3.1 Representing the frequency of each pattern as a binary expansion

The bilinear terms in the left-hand side of constraints (1d) can be circumvented in the following way: let \(x_{ki}\) and \(y_k\) be as defined in the previous section, and let \(z_k = \displaystyle \sum \nolimits _{j \in J_k} 2^j z_{kj}\), where:

\(J_k = \{0, 1, \ldots , 1+ {\lfloor }\log _2 (M^k){\rfloor }\}\)

is the set of bits to represent the frequency of

pattern \(k \in K\); and

\(z_{kj} \in \{0,1\}\)

is the binary variable for bit \(j \in J_k\) of pattern \(k \in K\).

The bilinear constraints (1d) are reformulated as:

$$\begin{aligned}&\sum _{k \in K} \sum _{j \in J_k} 2^j z_{kj} x_{ki} \ge d_i,&i \in I, \end{aligned}$$

which can be replaced by a set of disjunctive inequalities that expresses the terms \(w_{kij} = z_{kj} x_{ki}\), \(k \in K\), \(i \in I\), and \(j \in J_k\) in a linear form (Harjunkoski et al. 1996). Having defined all the parameters and variables, we formulate a bi-objective integer linear programming formulation for the CSP-S in model (2). We refer to this model as Model-A.

$$\begin{aligned} \mathbf{Minimize}&\quad \sum _{k \in K} \sum _{j \in J_k} 2^{j} z_{kj}.&\end{aligned}$$
(2a)
$$\begin{aligned} \mathbf{Minimize}&\quad \sum _{k \in K} y_k.&\end{aligned}$$
(2b)
$$\begin{aligned} \mathbf{subject} \,\mathbf{to}&\nonumber \\&\sum _{i \in I} l_i x_{ki} \le L y_k,&k \in K. \end{aligned}$$
(2c)
$$\begin{aligned}&\sum _{k \in K} \sum _{j \in J_k} 2^{j} w_{kji} \ge d_i,&i \in I. \end{aligned}$$
(2d)
$$\begin{aligned}&\sum _{j \in J_k} 2^j z_{kj} \le M^k y_k,&k \in K. \end{aligned}$$
(2e)
$$\begin{aligned}&\sum _{j \in J_k} 2^{j} z_{kj} \ge \sum _{j \in J_{k+1}} 2^{j} z_{(k+1)j},&k \in K\backslash \{N\}. \end{aligned}$$
(2f)
$$\begin{aligned}&w_{kij} \le x_{ki},&k \in K, i \in I, j \in J_k. \end{aligned}$$
(2g)
$$\begin{aligned}&\sum _{i \in I} w_{kij} \le \sum _{i \in I} O^i z_{kj},&k \in K, i \in I. \end{aligned}$$
(2h)
$$\begin{aligned}&w_{kij} \ge x_{ki} - O^i(1-z_{kj}),&k \in K, i \in I, j \in J_k. \end{aligned}$$
(2i)
$$\begin{aligned}&x_{ki} \in {\mathbb {Z}}_+, x_{ki} \le O^i,&k \in K, i \in I. \end{aligned}$$
(2j)
$$\begin{aligned}&z_{kj} \in \{0,1\},&k \in K, j \in J_k. \end{aligned}$$
(2k)
$$\begin{aligned}&y_{k} \in \{0,1\},&k \in K. \end{aligned}$$
(2l)
$$\begin{aligned}&0 \le w_{kij} \le O^i,&k \in K, i \in I, j \in J_k. \end{aligned}$$
(2m)

Objective function (2a) minimizes the number of objects, and objective function (2b) minimizes the number of patterns. Constraints (2c) ensure that the sum of the length \(l_i\) of the items does not exceed the length L of the object, for each pattern \(k \in K\). Constraints (2d) ensure that the demand of each item type \(i \in I\) is fulfilled exactly or in excess. Constraints (2e) enforce that \(y_k=1\) when the frequency of pattern \(k \in K\) is not zero (i.e., \(\sum _{j \in J_k} 2^j z_{kj} > 0\)). Valid inequalities (2f) ensure that the patterns are sorted in a non-increasing order of their frequencies. Constraints (2g), (2h), and (2i) are the set of disjunctive linear inequalities that formulates the expression \(w_{kij} = z_{kj} x_{ki}\), \(k \in K\), \(i \in I\), and \(j \in J_k\). In other words, these constraints enforce that \(w_{kij} = 0\) when \(z_{kj} = 0\), and \(w_{kij} = x_{ki}\) when \(z_{kj} = 1\). Constraints (2j) to (2m) define the domain of the variables.

3.2 A novel pseudo-polynomial ILP formulation

In this section, we present an alternative modeling approach that links the pattern and its frequency in a single decision variable. Then we make use of several knapsacks represented by disjunctive inequalities to guarantee the feasibility of the patterns. Thus, we now redefine sets \(J_k\) to be:

$$\begin{aligned} J_k = \{0,1,\ldots ,M^k\} \hbox { is the set of possible frequencies of pattern } k \in K. \end{aligned}$$

The two sets of variables of the proposed model are as follows:

\(\lambda _{kj}\)

binary variable that equals (1), if pattern \(k \in K\) has frequency \(j \in J_k\), and (0),

otherwise;

\(\alpha _{kji}\)

integer variable that represents the number of items of type \(i \in I\) that are produced

when cutting one object with pattern \(k \in K\) that has frequency \(j \in J_k\backslash \{0\}\).

Having defined all the parameters and variables, we formulate a novel bi-objective integer linear programming formulation for the CSP-S in model (3). We refer to this model as Model-B.

$$\begin{aligned} \mathbf{Minimize}&\quad \sum _{k \in K} \sum _{j \in J_k} j \lambda _{kj}.&\end{aligned}$$
(3a)
$$\begin{aligned} \mathbf{Minimize}&\quad \sum _{k \in K} \sum _{j \in J_k} \lambda _{kj}.&\end{aligned}$$
(3b)
$$\begin{aligned} \mathbf{subject} \,\mathbf{to}&\nonumber \\&\sum _{i \in I} l_i \alpha _{kji} \le L \lambda _{kj},&k \in K, j \in J_k\backslash \{0\}. \end{aligned}$$
(3c)
$$\begin{aligned}&\sum _{k \in K} \sum _{j \in J_k\backslash \{0\}} j \alpha _{kji} \ge d_i,&i \in I. \end{aligned}$$
(3d)
$$\begin{aligned}&\sum _{j \in J_k} \lambda _{kj} = 1,&k \in K. \end{aligned}$$
(3e)
$$\begin{aligned}&\sum _{j \in J_k} j \lambda _{kj} \ge \sum _{j \in J_{k+1}} j \lambda _{(k+1)j},&k \in K\backslash \{N\}. \end{aligned}$$
(3f)
$$\begin{aligned}&\lambda _{kj} \in \{0,1\},&k \in K, j \in J_k. \end{aligned}$$
(3g)
$$\begin{aligned}&\alpha _{kji} \in {\mathbb {Z}}_+, \alpha _{kji} \le O^i,&k \in K, j \in J_k\backslash \{0\}, i \in I. \end{aligned}$$
(3h)

Objective function (3a) minimizes the number of objects, and objective function (3b) minimizes the number of patterns. Constraints (3c) ensure that the sum of the length \(l_i\) of the items does not exceed the length L of the object for each pattern \(k \in K\) of frequency \(j \in J_k\). Note that these constraints are also disjunctive inequalities that enforce \(\sum _{i \in I} \alpha _{kji} = 0\), when \(\lambda _{kj} = 0\), for each \(k \in K\) and \(j \in J_k\backslash \{0\}\). Constraints (3d) ensure that the demand of each item type \(i \in I\) is fulfilled exactly or in excess. Constraints (3e) ensure that each pattern \(k \in K\) has only one frequency \(j \in J_k\) (sets \(J_k\) include the value of zero). Valid inequalities (3f) ensure that the patterns are sorted in a non-increasing order of their frequencies. Constraints (3g) and (3h) define the domain of the variables. We chose to not define variables \(\alpha _{kji}\) when \(j = 0\), because these variables would not have a contribution in the left-hand side of constraints (3d).

In Table 1, we present the number of variables and constraints of Model-A and Model-B in terms of the problem instance and sets \(J_k\).

Table 1 Number of variables and constraints of the ILP models
Full size table

We highlight the importance of the proposed upper bound \(M^k\) used to define sets \(J_k\) in order to obtain a model with fewer variables and constraints, which is usually helpful to accelerate the convergence of the branch-and-bound procedure in the context of an ILP solver. This is in contrast, for example, with Harjunkoski et al. (1996) who when addressing a mono-objective optimization problem, suggested the constant \({\bar{M}}^k = \sum _{i \in I} d_i\), \(k \in K\). Note that the parameters M and N also affect the number of variables and constraints of Model-A and Model-B, and so they are analyzed in the next section.

4 A framework for generating the Pareto optimal frontier

We develop a straightforward framework that makes use of either of the two models proposed in the previous section to generate the Pareto optimal frontier for the CSP-S. For this purpose, we first discuss a simple preprocessing operation. Let \(E = (M, l = (l_1, \ldots , l_M)^\top , d = (d_1, \ldots , d_M)^\top , L)\) be a problem instance of the CSP-S. We seek to obtain an equivalent instance by modifying single input data as follows:

  1. (P1)

    Two item types \(a \in I\) and \(b \in I\), \(a < b\), with the same length (i.e., \(l_{a} = l_{b}\)) are aggregated. In other terms, we set \(d_{a} := d_{a} + d_{b}\), and then item type b is removed from set I.

Other authors also considered using (P1) before solving the problem instance (Lee 2007; Golfeto et al. 2009; Araujo et al. 2014). At first, (P1) is relevant to reduce the number M of (different) item types. In addition, we highlight its relevance to avoid loss of optimality in Preposition 1:

Proposition 1

A problem instance \(E \!=\! (M, l \!=\! (l_1, \ldots , l_M)^\top , d \!=\! (d_1, \ldots , d_M)^\top , L)\) with two or more item types of the same length considered as different item types may lead to loss of optimality.

Proof

Consider a problem instance \(E = (2, l = (l_1,l_2)^\top , d = (d_1,d_2)^\top , L)\), where \(L/2 < l_a = l_b \le L\). For this non-aggregated instance, the Pareto optimal frontier has a single cutting plan with two patterns, that is, a first pattern with a single item of type 1 (frequency of \(d_1\)), and a second pattern with a single item of type 2 (frequency of \(d_2\)). However, if we apply (P1), then we obtain an equivalent instance \({\bar{E}} = (1, l = (l_1)^\top , d = (d_1+d_2)^\top , L)\) that reaches an optimal cutting plan of one pattern with a single item of type 1 (frequency of \(d_1 + d_2\)). \(\square \)

We focus now on the two nadir vectors, which are the two solutions in the Pareto optimal frontier characterized by having the minimum value in one objective function and the maximum value for the other objective function. Thus, let:

\(z^*\)

minimum value on the number of objects, which we obtain by solving the arc-flow model

of Valério de Carvalho (1999, 2002) for the CSP;

\(y^*\)

minimum value on the number of patterns, which we obtain by solving the associated Bin

Packing Problem (BPP), where the demand of all item types \(i \in I\) is set to \(d'_i = 1\).

Notice that we also obtain parameter N as a result of solving the arc-flow model and post-processing the solution into a cutting plan. And, we also obtain parameter \({\overline{z}}\) as a result of solving the associated BPP, where each bin represents a pattern whose frequency is post-processed to be equal to the highest (original) demand \(d_i\) of its packed items.

In Algorithm 1 we present a pseudocode of the developed framework for generating the Pareto optimal frontier for the CSP-S, taking into account Model-B. It is easy to adapt the algorithm to make use of Model-A. Algorithm 1 consists of solving the version of Model-B that minimizes the number of objects subject to a limited number of patterns in a iterative manner, which starts as \({{\mathbf {y}}} := y^*\) patterns and increases by one unit in each iteration. In contrast, the number of objects \({{\mathbf {z}}}\) tends to decrease as the algorithm iterates. Note that if a (short) time limit is considered as an additional stopping criterion on the execution of the ILP solver, then there is no guarantee to obtain efficient solutions only. We alter the (real) size of the model to be solved (i.e., the number of variables and constraints) in line 9 of Algorithm 1, since the presolve of the ILP solver will consider the variables with the same lower and upper bounds as constants. Thus, we expect the solver to find an optimal solution more quickly in the first iterations of the algorithm. We emphasize that one could limit the solution space of each iteration of the algorithm to exactly \({\mathbf {y}}\) patterns. However, we chose to limit the solution space to up to \({\mathbf {y}}\) patterns so that the solution from the previous iteration would also be feasible for the current iteration.

figure a

Additional preprocessing operations could be done in line 1 of Algorithm 1. For instance, removing an item type \(i \in I\) that \(l_i + \min _{i \in I} \{l_i\} > L\), or the reduction method to decrease the length L of the object and increase the length \(l_i\) of the item types (Scheithauer 2018). We chose to not consider these preprocessing operations because we also report results on trim loss in Sect. 5.

4.1 An illustrative example

In Table 2, we provide an illustrative problem instance of the CSP-S, initially proposed in Haessler (1975). In Fig. 1 we illustrate the Pareto optimal frontier of this instance obtained with Algorithm 1 considering Model-B. In Table 3, we present details on the cutting plan of 6 patterns and 25 objects, where each item type is represented by its length and its number of copies is in parenthesis. For this example, we note that Vahrenkamp (1996) found a cutting plan of 20 patterns and 25 objects, which is essentially different from the solution presented in this table.

Table 2 An illustrative example of the CSP-S with \(L=141{,}000\) and \(m=27\) item types (Haessler 1975)
Full size table
Fig. 1
figure 1

Pareto optimal frontier of the illustrative example defined in Table 2

Full size image
Table 3 A cutting plan of 6 patterns and 25 objects for the illustrative example defined in Table 2
Full size table

We also generated the Pareto optimal frontier of this instance for the case in which the demand of the items should be fulfilled exactly (without surplus), i.e., we changed the sign of constraints (3d) from \(\ge \) to \(=\). For this new case, the Pareto optimal frontier has a single cutting plan of 6 patterns and 25 objects. In other words, there is no cutting plan with less than 6 patterns that fulfills exactly the demand of the items for this instance. Note that additional patterns could be required in this new case in order to reach a solution with the minimum number of objects, but this was not the case for this instance.

5 Computational experiments

In this section we present the results of computational experiments performed with the developed framework with Model-A and Model-B. This section is divided into three parts. In Sect. 5.1, we consider 90 problem instances (out of 1800) randomly generated by problem generator CutGen1 (Gau and Wäscher 1995). We used them to assess the relative performance of the mono-objective versions of the proposed models in order to report information about the number of variables and constraints, the value of the linear relaxation, and, especially the scenarios in which the models perform better or worse. In Sect. 5.2, we consider 40 problem instances taken from a real fiber company in Japan (Umetani et al. 2003), which were used to assess the performance of the developed framework with the models to generate the Pareto optimal frontier. We considered the Pareto frontiers provided in Umetani et al. (2003) and Lee (2007) as benchmark approaches. In Sect. 5.3, we present a brief discussion of the ILP formulations of Johnston and Sadinlija (2004) and Alves and Valério De Carvalho (2008) with some additional results. All the instances are available at https://sites.google.com/site/shunjiumetani/benchmark, and they are further detailed at the beginning of each section. Our approaches were coded in C++, using the GUROBI v.9.1.1 as the general-purpose ILP solver. The experiments were carried out on a PC with an Intel Xeon E5-2680 (2.7 GHz), limited to 4 threads, 32 GB of RAM, running the Ubuntu 16.04 LTS Operating System.

5.1 Results for CutGen1 instances

Foerster and Wäscher (2000) used the problem generator CutGen1 to randomly generate a set of instances with 18 different classes for the CSP-S. A class is characterized by the number of item types (M), the length of the object \(L=1,000\), the values \(v_1\) and \(v_2\) that determine the length of the items in the interval \([ v_1 L , v_2 L ]\), and the average of the demands (\(d_{av}\)) for each item type. These classes are divided into three groups: (G1) six classes of small items (\(v_1=0.01\) and \(v_2=0.20\)), (G2) six classes of assorted items (\(v_1=0.01\) and \(v_2=0.80\)), and (G3) six classes of large items (\(v_1=0.20\) and \(v_2=0.80\)). Parameter M assumes the values of 10, 20, and 40 item types, while parameter \(d_{av}\) assumes the values of 10 and 100 copies of items. For each class, they generated 100 instances, but we considered here just the first 5 instances generated for each class in a total of 90 (\(=\)18\(\times \)5) instances.

We considered the weight sum method with unitary costs \(c_o\) and \(c_p\) to obtain mono-objective ILP formulations derived from Model-A and Model-B, similar to what was discussed in Sect. 2. As in Cui et al. (2015), we used \(c_o = 1{,}000\) and \(c_p = 100\), which tend to cause a lexicographic hierarchy in the two objective functions. Thus, we carried out lines 1 to 4 in Algorithm 1 with the adaptation in the objective function, and then executed the solver with a time limit of 3600 s. For each class of instances, we report the class identification, the number of item types (M), the values of \(v_1\) and \(v_2\) and the average demand (\(d_{av}\)) in Table 4. For Model-A and Model-B and each class of instances, we also report the number of variables (var), number of constraints (cons), relative optimality gap in percentage (gap[%]), processing time in seconds (time [s]), value of the linear relaxation (LR), and number of instances in the class with certificate of optimality (opt). The relative optimality gap is calculated as \(100 \times (z_p - z_d)/ z_p\), where \(z_p\) is the incumbent objective value and \(z_d\) is the lower bound.

The results in Table 4 show that the solver with Model-A obtained average gaps of 1.69% (2203.59 s), 10.00% (2304.26 s) and 14.80% (2,544.21 s) for instances of groups G1, G2 and G3, respectively, while the solver with Model-B obtained average gaps of 1.04% (1,838.50 s), 5.59% (2344.94 s) and 11.29% (2567.69 s). The optimality was proven by the solver in 34 (out of 90) instances with Model-A and in 40 (out of 90) instances with Model-B. As expected, the models performed better (resp. worse) in those classes with small (resp. large) values of the number of item types (M) and/or (resp. large) small value of the average demand (\(d_{av}\)). For instance, the optimality was proven by the solver with Model-B in all instances of classes 1, 3 and 5 of group G1, where these classes have \(d_{av}=10\). In contrast, the average gaps are higher for both models in classes 6, 12 and 18, which have \(M=40\) and \(d_{av}=100\). We ran additional computational experiments with Model-B considering all 100 instances in classes 1, 3, 7, and 13. The optimality was proven by the solver in all these 400 (\(=\)4\(\times \)100) instances. The average number of objects (setups) obtained by the solver with Model-B was 11.48 (2.90), 22.13 (4.19), 50.24 (6.32), and 63.47 (7.51) in classes 1, 3, 7, and 13, respectively. As a comparison, for these classes, the state-of-the-art heuristic of Cui et al. (2015) reported 11.49 (3.73), 22.13 (5.42), 50.24 (6.40), and 63.47 (7.52). For both models, we believe that a longer time limit would contribute to obtaining more certificates of optimality only in classes with up to \(M=20\) item types or \(d_{av}=10\), given that most of the time spent by the solver is to prove the optimality of the solution.

We note the quality of the linear relaxation of Model-B in comparison to Model-A reported in Table 4. For instance, the average values of the linear relaxation of Model-A and Model-B in class 1 was 1465.33 and 10,984.99, respectively, while the average value of the optimal solutions was 11,720.00. However, the quality of the linear relaxation of Model-B tends to decrease as the number of variables and constraints also increase. For example, the average values of the optimal solutions in classes 7 and 13 were 51,820.00 and 63,580.00, respectively. Indeed, the number of variables and constraints of both models increase as the number of item types also increases; they increase quickly as the average demands also increase, but notably in Model-B. In summary, Model-B outperformed Model-A in instances of group G1, while both models performed similarly in groups G2 and G3, with better average gaps for Model-B, and slightly better average times for Model-A.

Table 4 Results for the CutGen1 instances
Full size table

5.2 Results for Fiber instances

In this section, we present the results performed to assess the quality of the Pareto frontiers obtained by the developed framework of Sect. 4 with Model-A and Model-B. We limited each execution of the solver to 900 s and stopped the algorithm if there was no improvement in reducing the number of objects for three consecutive iterations. We considered the set of 40 practical instances for the CSP-S provided by Umetani et al. (2003) which were taken from a chemical fiber industry. In these instances, the number of item types M varied from 6 to 29, the length of the items varied from 500 to 2000, and the demand of each item type varied from 2 to 264. They were divided into two groups: the first twenty instances had \(L=5180\) and the remaining twenty instances had \(L=9080\). After applying preprocessing (P1) of Algorithm 1, the number of item types M varied from 4 to 20. The heuristic approaches of Umetani et al. (2003), Lee (2007), Golfeto et al. (2009) and Araujo et al. (2014) for the CSP-S used these instances to provide solutions with minimum trim loss for different fixed numbers of patterns. They calculated the trim loss as the percentage ratio of the total trim loss to the total length of the items, i.e., \(100\times (L {\hat{z}} - \sum _{i \in I} l_i d_i)/\sum _{i \in I} l_i d_i\), where \({\hat{z}}\) is the number of objects required in the cutting plan. As we are not aware of other approaches in the literature that have solved the CSP-S exactly, we considered the approaches of Umetani et al. (2003) and Lee (2007) as benchmark approaches, denoted as ILS03 and Crawla, respectively. We note that the performance of the algorithms of Lee (2007) and Golfeto et al. (2009) was similar, while the genetic algorithm of Araujo et al. (2014) found more solutions with minimum trim loss, but required a significant additional number of patterns.

In Tables 5 and 6, we report the Pareto frontiers obtained by ILS03, Crawla, Model-A and Model-B for this set of instances where \(L=5180\) and \(L=9080\), respectively. For each of the approaches, we present the percentage of trim loss obtained by the approach when considering the respective number of patterns (column y). For Model-A and Model-B, we report three additional pieces out information. The first is the processing time in seconds required to generate the Pareto frontier, which is reported in italic on the same line of the instance name. Then we report their entries of percentage trim loss in bold, when the optimality was proven by the solver. Finally, we use the symbol * to indicate when the approach was not able to find a cutting plan with the minimum amount of trim loss, which is indicated in parentheses next to the instance name, when neither Model-A nor Model-B was able to achieve the minimum. Since the computational environment of the benchmark approaches is less powerful, we limit the analysis to the quality of the solution next. We note that ILS03 was executed in seconds/minutes (Umetani et al. 2003), while Crawla required from 1 to 20 min (Lee 2007).

Table 5 Results for the Fiber instances of \(L=5180\)
Full size table
Table 6 Results for the Fiber instances of \(L=9080\)
Full size table

The results in Tables 5 and 6 show that the Pareto optimal frontier was obtained by Model-A and Model-B in 26 (out of 40) instances. In addition, Model-A found the solution with minimum trim loss in instance fiber17_5180, while Model-B in instance fiber20_5180. The processing times of Model-B were better than those of Model-A in almost all instances. We highlight the quality of the Pareto frontiers of Model-A and Model-B in comparison to ILS03 and Crawla. For instance, in fiber13a_5180, ILS03 ranged from 10 to 14 patterns, while Crawla and the proposed approaches required less than half that number of patterns. Note that Crawla did not report results in this instance for y = 2, and obtained much higher trim loss values than the proposed approaches for y = 3 and y = 4. We did not report in bold, but we highlight that Crawla found a few optimal solutions, for instance, in fiber07_5180 and fiber09_5180. Considering instances with approximate Pareto frontiers as in fiber29a_5180, the trim loss values obtained by Model-A and Model-B were considerably lower than the benchmark approaches. As expected, these results show that increasing the number of patterns significantly reduces the trim loss in the first cutting plans of the Pareto curve (i.e., when y is close to \(y^*\)), as shown in Table 6. In the last cutting plans of the Pareto curve when z is close to \(z^*\), this behavior was attenuated, as shown in Table 5. We also note the cases of fiber06_5180 (y from 3 to 4) and fiber14_5180 (y from 5 to 6), in which the trim loss remained even with the increase in the number of patterns. In summary, the better results in Table 6 than in Table 5 can be explained by the increase of L from 5180 to 9080. Since the length of the item types is maintained, this increase requires cutting planes with fewer objects, which, in turn, requires fewer variables and constraints.

5.3 Comments on other ILP formulations

In the development phase of this study, we performed preliminary computational experiments with the ILP formulations of Johnston and Sadinlija (2004) and Alves and Valério De Carvalho (2008) that can be adapted to address the CSP-S. Since the variables in these formulations are indexed in the number of items that fit in the object, they tend to have a better (resp. worse) performance when the number of items in a pattern is small (resp. large). For instance, for the Cutgen1 instances, the optimality was proven by the solver with the adapted version of the arc flow model of Alves and Valério De Carvalho (2008) in 1 out of 30 instances in group G1 and in 25 out of 30 instances in group G3. Certificates of optimality were obtained by the solver with the adapted version of the model of Johnston and Sadinlija (2004) in 9 out of 30 instances in group G1 and in 12 out of 30 instances in group G3. Note that the average number of items in a pattern of group G3 was 2 (\(v_1=0.20\) and \(v_2=0.80\)). Another difficulty was in the instances with large values for the maximum frequency of the patterns, especially in the first cutting plans of the Pareto curves for the Fiber instances. Indeed, the framework of Sect. 1 reached the stopping criterion without solutions in 19 out of 40 of Fiber instances with this formulation. Therefore, we consider that the proposed pattern-based formulations were more suitable for the practical scenarios we intend to solve.

6 Conclusions

We proposed an exact framework to obtain the Pareto optimal frontier for the One-dimensional Cutting Stock Problem with the bi-objective function of minimizing the number of objects and the number of distinct patterns. Instead of using decomposition methods for solving the Pattern Minimization Problem as in Vanderbeck (2000), we relied on the development of ILP formulations to be solved by a general-purpose solver. The results of the computational experiments showed that the approaches are appropriate for instances with solutions characterized by a moderate number of objects and a few patterns in the Pareto optimal frontier. As future research, a challenging possibility is the development of new valid inequalities to strengthen the linear relaxation of the ILP formulations, as well as to avoid symmetries in the solutions. Since the problem is mainly addressed by heuristics, another possibility would be the development of a highly flexible algorithm based on a Sequential Heuristic Procedure. This algorithm would identify the characteristics of the problem instance, for instance, to generate patterns, by closing the demand of more than one item type and to consider patterns with trim loss, as in the illustrative example provided.