A method for demand-accurate one-dimensional cutting problems with pattern reduction

1.   Introduction

The classical one-dimensional cutting stock problem (1D-CSP) is a typical combinatorial optimization problem. In the 1D-CSP, there are m items with lengths (l₁..., l_m) and demands (d¹, d²..., d^m) that are cut from the stock objects of length L to minimize the material cost. The first notable research result in solving the 1D-CSP was based on the simplex column generation method ^[1]. In most of the existing studies, it is challenging to optimize the material cost and setup cost simultaneously, and fewer patterns lead to higher material costs ^[2,3,4,5].

In practice, the position of the cutting tool in the cutter must be adjusted every time before another cutting pattern is switched. Therefore, the time cost of adjusting the position of the cutting tool in the machine equipment cannot be ignored ^[6,7,8].

The algorithm proposed to solve the 1D-CSP model is called the variable-to-constant (VTC) algorithm. The demands of the items in the model must be precisely satisfied. It solves the 1D-CSP in two stages. In the first stage, it uses a column generation method to obtain the lower bound (LB), which is the minimum value of the number of stock objects used (material cost). In the second stage, VTC is used to generate the cutting patterns and to obtain a new objective function value. If the objective function value is less than or equal to the LB, the calculation is stopped. Otherwise, the calculation is continued by iterating m times or 2m times (each new cutting pattern generated is considered one iteration) to obtain a feasible initial solution. In parallel, the new method is fused with two authoritative methods in the literature to verify the validity of the methodology proposed in this paper.

1.1.   Literature review

For cutting problems, López de Lacalle et al. ^[9] proposed a technical model to estimate the value of cutting forces, providing manufacturers with the opportunity to reduce production and delivery times. Approaches for determining the integer solution to the 1D-CSP (the demand is met exactly) fall into two main categories: heuristic approaches construct a good cutting pattern and use it as much as possible (constructive heuristics) and heuristic approaches round the relaxation solution (residual heuristic). Hinxman et al. ^[10] provided a detailed description of constructive heuristics, such as the first-fit decreasing (FFD) algorithm. The core of FFD is to first place the largest item into the pattern with the highest possible number of cutting patterns and no more than the demand. If the largest item no longer fits that cutting pattern, the second largest item is selected, and so on. The greedy heuristic follows the same philosophy as the FFD heuristic, but without prioritizing the largest items to construct the new cutting pattern. Later, Ongkunaruk et al. ^[11] modified the FFD heuristic to solve the bin packing problem (BPP). In 2009, the FFD and greedy heuristics were further modified to allow the redesign of cutting patterns with undesirable residues ^[12]. Specifically, such cutting patterns are not large enough to continue to be used or not small enough to be accepted as waste. In the same year, Poldi and Arenales ^[13] proposed three versions of greed-based residual heuristic rounding techniques, namely, GRH1, GRH2 and GRH3. Their core ideology is also based on using the relaxation solution to obtain the approximate integer solutions. In contrast, Cui et al. ^[14] solved the one-dimensional cutting problem for multiple stock objects in two stages. The first stage uses a pattern-set generation algorithm to generate patterns and combine them with column generation techniques to solve the residual problems. In the second stage, to further reduce the material cost indicator, the ILP model is solved using the CPLEX solver as a way to obtain a solution for stage two. The best solution for both phases is selected. In their second-stage solution method, overproduction occurs.

Recently, new research has been conducted to advance the development in this field. For example, a modified greedy heuristic (MGH) was proposed to optimize material cost ^[15]. It shows more promising integer solutions than other methods but does not obtain the best cutting pattern (losing to the GRH algorithm in terms of pattern reduction). One thing in common among these methods is that they are all based on the slack solution of the column generation method to perform rounding to obtain the integer solution.

Here, we also give an overview of the literature on the cutting stock problem with setup cost (CSP-S). The sequential heuristic procedure of Haessler ^[16] was one of the first methods to deal with the CSP-S. It is essential to address the CSP-S in order to find the optimal trade-off between the numbers of objects and patterns ^{[17,18,19,20]}. Other SHP-based approaches can be found; for example, Mobasher and Ekici ^[21] proposed two local search algorithms and a column generation-based heuristic algorithm for CSP-S in order to minimize the total production cost, including material and setup costs. Cui et al. ^[4] presented a heuristic algorithm to deal with the CSP-S in two stages. In the first stage, they first used the heuristic to generate cutting patterns. In the second stage, based on the optimizer solver, a bi-objective optimization model of material and setup costs was developed to further reduce the setup cost. Martin et al. ^[22] modified Haessler's sequential heuristic procedure, but only individual instances were tested better than the other methods, and most instances were tested to perform poorly. Lately, Martin et al. ^[5] proposed a pattern-based pseudo-polynomial ILP formulation to solve the CSP-S, which depends on an upper bound on the maximum frequency of each pattern in the cutting scheme. We must emphasize one point: The current research works for solving the CSP-S allow for overproduction (Ax ≥ d) in their models. In contrast, in the mathematical model developed in this study, the demand must be exactly satisfied (Ax = d).

A problem associated with pattern reduction is the pattern minimization problem (PMP). This is a problem of minimizing the number of patterns with a finite number of objects, and it is a nonlinear integer programming problem. It is well known that the PMP was proven to be a hard NP problem by McDiarmid ^[23]. Some exact methods for solving the PMP exist in the literature, and the solutions of these algorithms have met the demand exactly without overproduction ^{[24,25,26,27,28]}. Vanderbeck ^[24] reformulated the PMP model by using the Dantzig-Wolfe decomposition principle and adapted it to integer programming. The authors did this by dualizing the relevant nonlinear constraints in a Lagrangian fashion, and the problem was decomposed into K identical subproblems. They solved these subproblems to generate new columns. The experiments indicated that this exact algorithm reduced the number of setups by an average of 63% compared to the initial solution to the standard cutting problem. Alves and de Carvalho ^[26] further improved the model proposed by Vanderbeck ^[24] by adding a constraint on the total waste to the subproblem. This allows the number of column-generated subproblems (knapsack problems) to be solved to be significantly reduced. They treated the LP-optimal solution as an arc-flow formulation with an integer variable and used the branch-and-price-and-cut algorithm to solve the master problem. However, because of the branching constraint and the fact that the demand is exactly satisfied, the solution is forced to exceed the maximum waste of the optimal 1D-CSP solution. In Alves et al. ^[27], the authors developed a CP model to derive two tighter LBs for the PMP. They also used the CP model to derive some efficient inequalities to deal with the hard constraints. From the experimental results of the 16 tested real-life cases, only three had worse LBs than those of Vanderbeck ^[24]. Three others had tighter LBs, while the remaining 10 cases had the same LBs. The above-mentioned developers of the three exact algorithms for solving the PMP did not report material usage cost in the experiments they conducted. Afterward, Mobasher and Ekici ^[8] briefly stated that the main drawback of the PMP model (Vanderbeck's model) is the weak LP relaxation bound. In addition, this compact model has to meet the demand exactly without allowing overproduction. This may increase the amount of material used and the number of different patterns used.

In conclusion, several of the above-mentioned exact methods for solving PMP models that have appeared thus far are computationally time-consuming (2 h per instance). In particular, their solution accuracy is very low for larger demands or problems with dimensionality greater than 20. However, the current literature shows that several residual heuristics can solve the 1D-CSP model with a single objective of material cost very well and with a short computational time. In their models, the demands are precisely satisfied. The shortcoming of the current solutions for such a 1D-CSP is that the cutting pattern cannot be reduced ^[15].

1.2.   Our contributions

In this paper, the solution algorithm (VTC) for the 1D-CSP is developed by considering the requirements of item production in practical applications (the demands for the items must be met precisely). The authors provide important contributions in this domain. They rely on a mathematical model that is built to obtain the solution. In our approach, the feasible solution for the 1D-CSP is obtained by updating the established mathematical model once for each generated cutting pattern. Our approach attempts to form a linear relationship between the patterns and the variables by fixing one of the decision variables as a constant. Meeting the demand precisely is not conducive to the reduction of cutting patterns and minimization of material cost ^[8]. Two sets of well-known benchmark examples from the literature and a set of real instances are used to evaluate the advantages or disadvantages of the algorithms. The results indicate that the implementation of the new approach using a generic ILP solver (Gurobi) is able to obtain the optimal solution for the 1D-CSP in some instances and to acquire fewer cutting patterns.

2.   Problem definition and mathematical formulations

In this section, we formally describe the 1D-CSP define some necessary notations and solve its relaxation solution by using the column generation approach.

2.1.   Problem description

A 1D-CSP in which the demands are precisely met consists of the following parts: given an unlimited number of identical stock objects of length L (e.g., lengths of wood, aluminum alloy, rolls of paper), the mission is to cut ${d^i}$ pieces of items of length l_i for $i \in I$ = {1..., m} to meet the quantities produced for the various items, keeping the number of stock objects used to a minimum. To simplify the model, we use $p$ to define a pattern and its index. We also use $P$ to denote a set of patterns and the indices of the patterns. In the 1D-CSP, a pattern $p$ is represented by a column vector ${a}_{p} = ({a}_{1p}, \cdots, {a}_{ip}, \cdots, {a}_{mp}{)}^{t}$, where ${a_{ip}}$ denotes the number of items $i$ in the cutting pattern $p$. The pattern $p$ is required to fulfill

We define an integer decision variable by ${x_p}$ with each $p \in P$, referring to the number of cutting patterns $p$ used. ${d^i}$ represents the quantity corresponding to item $i$. Therefore, the main objective of the classic 1D-CSP is generally to minimize material cost (the number of objects used), and its mathematical model can be formulated as

2.2.   Column generation

Let us briefly describe the relaxed solution model for Eqs (3)–(5), where we simply remove the integer constraints. Furthermore, an initial feasible solution $\overline p \subseteq P$ can be easily achieved by initialization (e.g., through the use of heuristics to obtain this solution). Equations (3)–(5) then become

The optimization problem described by Eqs (6)–(8) is called the restricted master problem (RMP). The RMP can provide the basis matrix $B$ of the current iteration to update ${B^{ - 1}}$ in the objective function of the subproblem. The computation stops when the objective function value in Eq (9) is greater than zero. Otherwise, a new column $p \notin \overline p$ can be generated iteratively to reduce the objective function value in Eq (6), and it is added to the RMP. The resulting basis matrix $B$ is updated. The subproblem thus solved is as follows:

In (9), ${c_B}$ is a row vector with m columns and all its elements are one. $B$ is a matrix with m rows and m columns. ${a_p} = {({a_{1p}}, \cdots, {a_{1p}}, \cdots {a_{mp}})^t}$ denotes a variable cutting pattern, expressed as a column vector. In (10), ${a_{ip}}$ indicates the number of items i in a cutting pattern $p$, and ${l_i}$ refers to the length of item $i$. L is expressed as the length of the stock object. Constraint (11) prevents the number of items i in the cutting pattern $p$ from exceeding the total number demanded.

3.   Solution methods

3.1.   Our methodology for generating columns

In this section, we first build a new mathematical model and then solve it by using a new method called VTC. The new model for the 1D-CSP instances is built by fixing one of the decision variables as a constant. This enables a linear relationship between the decision variables and the columns (cutting patterns), which facilitates cutting pattern reduction. The main features of VTC are as follows.

1) In terms of pattern reduction, the solution quality of the method for some instances is much better than the solution quality of the standard 1D-CSP model. The demands ${d^i}$(i = 1..., m) in (4) are exactly satisfied.

2) In terms of constraints, the number of constraints is forced to increase after fixing one of the decision variables. Obtaining the solution is more time-consuming, which is not true for low-demand problems.

3) After fixing a decision variable as a constant, all decision variables $x = ({x_1}, \cdots, {x_m})$ and the new column ${a_p} = {({a_{1p}}, \cdots, {a_{ip}}, \cdots, {a_{mp}})^t}$ form a linear relationship. The objective function is transformed into a linear objective function related to the variable vector ${a_p}$.

To conveniently describe the solution process of the method in this paper, we first represent (1)–(5) in matrix form.

In (12), $x = {({x_1}, \cdots {x_n})^t}$ indicates the column vector of decision variables, and c = (1..., 1) is a row vector containing n columns, where all elements are equal to one. The column vector ${a_p}$ is a vector of variables, which we denote as ${a_p} = {({a_{1p}}, \cdots, {a_{ip}}, \cdots, {a_{mp}})^t}$. Constraint (16) enables all decision variables to be nonnegative integers. Constraint (13) enables the quantity of all items to be precisely as required (i.e., demands are met exactly). A represents an m $×$ n matrix in which each column is a cutting pattern. Its right end is a demand vector $d = {({d^1}, \cdots, {d^m})^{\text{t}}}$, expressing the number of different items produced. l = (l₁..., l_m) represents a row vector, where l_i denotes the size of the i^th item. L designates the length of the stock object. Constraints (14) and (15) indicate that the elements in the cutting pattern ${a_p}$ have to satisfy ${a_{1p}}{l_1} + \cdots + {a_{{\text{m}}p}}{l_m} \leqslant L,$ and $0 \leqslant {a_{ip}} \leqslant {d^i}, i = (1, \cdots, m)$, an integer.

3.1.1.   Mathematical modeling

To solve the optimization problem described in Section 3.1, we reconstruct the model of the 1D-CSP. We consider only m decision variables, i.e., their number is equal to the number of item types. Each iteration, which generates a new column, also represents the generation of a new cutting pattern ${p}$. Let us introduce a vector of integer column variables a_p which, for each $p \in P$, gives the number of items cut for each type of item in the cutting pattern $p$. Furthermore, we assume that the 1D-CSP for the k^th iteration with m decision variables and m items is established by generating the k^th column. Consequently, we express the mathematical model at each iteration in terms of the matrix and the vector.

The following notations are used to describe it:

$f(x)$ objective value (total number of stock objects used)

$x_{G}$ decision variable, which is currently fixed as a constant

$d_{k}$ column vector obtained by performing the elementary row transformation of a matrix on the demand vector ${d_{k{\text{ - }}1}}$

$\overline{d_{{k}}}$ column vector obtained by forcing the k^th element of ${d_k}$ to be 0

$s_{k-1}$ matrix obtained by performing the elementary row transformation of a matrix on matrix ${s_{k - 2}}$

$\overline{s_{k-1}}$ vector obtained by forcing all elements of the k^th row of the matrix ${s_{k{\text{ - }}1}}$ to 0

${ss }$ row vector constructed from the k^th row of ${s_k}$

${l}$ row vector representing the dimensions of the m items

a_p cutting pattern $p$ currently being solved

$t$ row vector with m columns and element values equal to one

$m$ number of item types

$K$ objective optimal LB, which can be obtained from the column generation algorithm

$A_{k}$ cutting scheme corresponding to the generation of the k^th column

The 1D-CSP model described is remodeled as

In the above model, the number of iterations k = 1, 2, 3..., n, where each iteration produces a new column and an objective function value. $\overline {{d_k}}$ and $\overline {{s_{k{\text{ - }}1}}}$ are distinct from the previous iterations at each iteration. That is, the objective function and constraints need to be updated for each iteration. Equation (17) indicates that the objective is to minimize the material cost (the number of objects used), where ${x_G}$ is equal to the value of the decision variable corresponding to column k at the previous iteration. Constraint (18) means that all decision variables are constrained to be greater than or equal to zero, except for the decision variable corresponding to column k. Constraint (19) limits the size of the space where the item is placed in the pattern a_p. Equation (20) is an equation constraint that arises after fixing a decision variable corresponding to the k^th column as a constant ${x_G}$. Equation (22) gives the initial matrices ${s_0}$, A₀ and ${d_0}$ created at the beginning iteration.

In an effort to determine an efficient solution to the above optimization problem, we present below the computational procedure that implements the new mathematical model constructed. The solution procedure is shown below.

Step 1: Input the initialization matrix for ${s_0}, {d_0}, {A_0}$ and set k = 1. Additionally, sort the items, i.e., ${l_1} > {l_2} > , \cdots, > {l_m}$ or ${l_1} < {l_2} < , \cdots, < {l_m}$.

Step 2: Update the objective function and constraints by $ss, \overline {{s_{k{\text{ - }}1}}}$ and $\overline {{d_k}}$. ss can be obtained by forcing the elements in row one to zero in matrix ${s_{k{\text{ - }}1}}$.

Step 3: Let the decision variable ${x_k}$ be a constant ${x_G}$.

Step 4: Use the Gurobi solver to solve the k^th mathematical model to obtain ${a_p}$.

Step 5: Go to Step 6 if $f(x) > K\mathop {}\limits^{} and\mathop {}\limits^{} k < \beta m\mathop {}\limits^{} (\beta = 1\mathop {}\limits^{} {\text{or}}\mathop {}\limits^{} \beta = 2)$; otherwise, stop the calculation. Record all cutting patterns produced and their decision variables.

Step 6: Compute $\overline {{s_{k{\text{ - }}1}}}$, a_p and ssa_p, and apply their results as the k^th column in $A$.

Step 7: Perform elementary row transformation on matrix $A$ while performing the same transformation on matrix ${s_{k{\text{ - }}1}}$ and matrix ${d_k}$ as that performed on matrix $A$.

Step 8: Let $k = k + 1,$ and return to Step 2.

Step 5 indicates that the method does not necessarily solve for the optimal solution. Each generation determines a cutting pattern a_p (Steps 2–8). For each cutting pattern solved, the objective function and constraints need to be updated once (Step 2). Steps 6 and 7 depict a matrix elementary row transformation after each updated column in A. In Step 1, different sequencing may result in different VTC calculations. The experiments conducted later in this paper rank the items from largest to smallest before solving.

3.1.2.   Numerical example

In this section, we present a simple example to illustrate the solution process of the VTC method proposed in this paper.

Example. Consider an instance of the 1D-CSP with m = 4 items and demand vector d₀ = (d¹, d², d³, d⁴) = (6, 10, 8, 5)^T. Assume that L = 300, l = (l₁, l₂, l₃, l₄) = (150, 50, 40, 10) and row vector t = (1, 1, 1, 1). We also assume that the column vector ${a_p} = \left({\begin{array}{*{20}{c}} {{a_{1p}}} \\ {{a_{2p}}} \\ {{a_{3p}}} \\ {{a_{4p}}} \end{array}} \right)$. Before the iterative calculation, the following matrix is first initialized.

We let

Meanwhile, we set

Using (12)–(16), we obtain the following objective problem:

This is subject to

As a result,

and

Concurrently, the LB K = $\left\lceil {5.9} \right\rceil$ = 6 is obtained by the column generation method, which is the minimum material cost. This can be used as a condition for whether the iterative calculation is stopped. Since ${f_0}(x) > K$, the calculation continues, and the next step involves generating new columns.

Iteration 1 (Column 1 is generated):

Replacing column 1 of ${A_0}$ in (26) with the unknown column vector ${a_p}$ and using (12)–(14), we obtain the following objective problem:

This is subject to

and

To simplify the tedious calculation of the matrix, we can express the first column in matrix ${A_1}$ as

Fixing the decision variable ${x_1}$ to 6, we obtain

Let $\left({\begin{array}{*{20}{c}} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}} \right) = \overline {{s_0}}$ and $\left({\begin{array}{*{20}{c}} 0 \\ {10} \\ 8 \\ 5 \end{array}} \right) = \overline {{d_1}}$; then, by observing the relationship between Eqs (30) and (34), (35)–(37) can be transformed into

Now, substituting Eqs (35)–(37) into (29), the objective function can be written as follows:

The constraints are as follows:

Constraints (41) to (44) are converted into matrix and vector forms:

The Gurobi solver is used to solve the above optimization problem. Therefore, we obtain

Accordingly, ${A_1}x$ is

Iteration 2 (Column 2 is generated):

Similarly, replacing column 2 of ${A_1}$ in Eq (48) with the unknown column vector a_p and using Eqs (12)–(14), we obtain the following objective problem:

This is subject to

Next, we formulate Eq (50) as (54) and simultaneously perform the same operation on matrix ${s_1}$, with the following result. Thus,

and then, ${s_0}$ in Eq (24) becomes ${s_1}$ in (55):

At this point, fixing the decision variable ${x_2}$ to 4, we obtain

Because ${s_1} = \left({\begin{array}{*{20}{c}} 1 & 0 & 0 & 0 \\ { - 1} & 1 & 0 & 0 \\ { - 1} & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}} \right)$ in (55), we can let $\left({\begin{array}{*{20}{c}} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ { - 1} & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}} \right) = \overline {{s_1}}$. Because ${A_3}x = \left({\begin{array}{*{20}{c}} 6 \\ 4 \\ 2 \\ 5 \end{array}} \right)$ in (54), we can let $\left({\begin{array}{*{20}{c}} 6 \\ 0 \\ 2 \\ 5 \end{array}} \right) = \overline {{d_2}}$. Then, Eqs (56)–(58) can be expressed as

Through Eqs (56)–(58) and (49), the objective function is easily formulated as

The constraints are as follows:

Constraints (62)–(65) are converted into matrix and vector forms:

Using row 2 of matrix ${s_2}$ as a row vector ss, such that $ss = (- 1, 1, 0, 0)$, (66) is as follows:

The Gurobi solver is used to solve the above optimization problem. Therefore, we obtain

In this way, ${A_2}x$ can be written as

Iteration 3 (Column 3 is generated):

Since f₂(x) > K, the calculation continues to produce the next column. The objective optimization problem is formulated as

This is subject to

The next step of expressing (73) as (77) while performing the same elimination operation as that performed for matrix ${s_2}$ results in the following:

Then, ${s_1}$ in (55) becomes ${s_2}$ in (78):

As such, fixing the decision variable ${x_3}$ to 2 gives

Then, let $\left({\begin{array}{*{20}{c}} 2 & { - 1} & 0 & 0 \\ { - 1} & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & { - 1} & 0 & 1 \end{array}} \right) = \overline {{s_2}}$, $\left({\begin{array}{*{20}{c}} 2 \\ 4 \\ 0 \\ 1 \end{array}} \right) = \overline {{d_3}},$ so that Eqs (79)–(81) are formulated as

For this iteration, the objective function can be represented as follows:

The constraints are as follows:

Constraints (85) to (88) are represented in matrix and vector forms:

Using row 3 of matrix ${s_3}$ as a row vector ss, such that $ss = (- 1, 0, 1, 0)$, (89) is as follows:

The Gurobi solver is used to solve the above optimization problem. Therefore, we obtain

Note that ${f_2}(x)$ has the same result as ${f_3}(x)$ and that ${A_3}x$ is the same as ${A_2}x$; Thus, ${A_3}x$ is as follows:

Iteration 4 (Column 4 is generated):

Because f₃(x) > K, the calculation continues. The objective optimization problem is described as follows:

This is subject to

Consequently, by the matrix elimination operation, Eq (96) can be presented as (100), and the result is as follows:

Additionally, ${s_2}$ in Eq (78) is written as ${s_3}$ below:

Observing the relationship between the matrix ${A_5}$ in Eqs (100) and (101), we conclude that the following equation holds:

Therefore, after fixing the decision variable ${x_4}$ to 1, the expressions for the other variables can be written as

Given that $\left({\begin{array}{*{20}{c}} 2 & { - 1} & 0 & 0 \\ { - 1} & 1 & 0 & 0 \\ { - 1} & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{array}} \right) = \overline {{s_3}}$ and $\left({\begin{array}{*{20}{c}} 2 \\ 4 \\ 2 \\ 0 \end{array}} \right) = \overline {{d_4}}$, Eqs (103)–(105) are described as

The objective optimization problem is as follows:

The constraints are as follows:

Consequently, Eqs (109)–(111) can be represented in matrix and vector forms:

Using row 4 of matrix ${s_4}$ as a row vector ss, such that $ss = (1, - 1, 0, 1)$, the constraint given by (113) can be written as

The Gurobi solver is used to solve the above optimization problem. Consequently, we obtain

Because ${f_4}(x) = K = 6$, the calculation is cut off. If ${f_4}(x) > K$, we can perform the same operation as the above operation and loop to generate a new column; the optimal outcome is as follows:

$Ax$ exactly meets the demand. That is, $Ax = d$. From the results, only two columns are needed to reach the optimal integer solution. As the decision variables ${x_1}$ and ${x_3}$ are zero, columns 1 and 3 are therefore invalid. In view of practical applications, it is beneficial to reduce the setup cost.

Note that our solution procedure for generating columns is relaxed with respect to the constraints on the decision variables (i.e., the decision variables are not restricted to integers). The experimental results show that integer solutions can be obtained. We elaborate further on how to deal with this problem.

3.2.   Other approaches

To produce an ideal or at least acceptable solution, we introduce several heuristics in some well-known literature. With respect to solving the 1D-CSP, there are two main types of methods, one being constructive heuristics, and the other being residual heuristics.

3.2.1.   Constructive heuristics

Constructive heuristics is a way of determining an integer solution to a one-dimensional cutting problem; specifically, it is a way of constructing a good cutting pattern and using as much of it as possible ^[10]. No items are allowed to be overproduced. Two well-known procedures for constructing cutting patterns are FFD and greedy approaches.

The general framework for constructive heuristics is as follows.

Step 1: Construct a good cutting pattern for a type of stock length.

Step 2: Among the cutting patterns generated in Step 1, select the one with minimum waste.

Step 3: Use the cutting pattern in Step 2 as much as possible without overproduction.

Step 4: Update the demand of the items.

Step 5: If the demand for each of these items is met precisely, stop. Otherwise, go to Step 1.

1) FFD heuristic

The procedure is to prioritize the largest item into the pattern until its demand is met. If the largest item cannot be placed, the second largest item is considered for placement, and so on. The cutting pattern is completed when all demands of the items have been precisely met.

2) Greedy heuristic

In this paper, the greedy procedure consists of solving the knapsack problem in Step 1, which has only one type of stock length as a raw material (stock object). The backpack problem appears as follows.

In (118), ${l_i}$ refers to the length of item type i, $i = 1, \cdots, m$ and ${r_i}$ is the residual demand for item type i. ${r_i}$ is updated in Step 4. At the beginning, ${r_i} = {d^i}$, and ${d^i}$ is the demand for item i, $i = 1, \cdots, m$.

3.2.2.   Residual heuristics

Residual heuristics produce an optimal integer solution for the continuous relaxation of (6)–(8). If at least one element of the relaxation solution vector is not a nonnegative integer, then we can use the residual heuristic for rounding. Otherwise, the relaxation solution is the optimal integer solution. The residual heuristics are described before we define a residual problem.

Definition 1 (Residual problem). Let $\overline x$ be an approximate integer solution rounded down for x. $\overline x = (\left\lfloor {{x_1}} \right\rfloor, \cdots, \left\lfloor {{x_m}} \right\rfloor)$. $r = d - A\overline x$ stands for the residual demand. We can formulate the residual problem in the form of (6) to (8), where demand $d$ varies with $r$.

Note that the cutting patterns of the optimization problem consist of two parts: the first part consists of the cutting patterns (columns) corresponding to the relaxation solution, and the second part consists of the cutting patterns generated by the residual problem.

The general framework for residual heuristics:

Step 1: Let $c = 0$ and ${r^c} = d$ be the initial data for the beginning residual problem.

Step 2: Solve the relaxation solution to the residual equation problem by using the column generation technique. Assume that the relaxation solution x comprises all nonnegative integers, and then stop. Otherwise, go to Step 3.

Step 3: Find an approximate integer solution ${\overline x ^c}$. If it is a null vector, go to Step 5.

Step 4: Update the demand for the residual problem, ${r^{c + 1}} = {r^c} - A{\overline x ^c}$. If ${r^c} = 0$, then stop. Otherwise, go to Step 2.

Step 5: Solve the remaining residual problem.

Whether this algorithm is considered good or bad is mainly related to determining how to go about rounding through Step 3 and how to solve for the remaining problem through Step 5. Nevertheless, Step 2 is even more critical when considering the auxiliary indicator (setup), as it can directly affect the number of cutting patterns. There are two main types of Step 3 rounding methods: one is downward rounding, as in the FFD and greedy approaches; the other is a downward or upward rounding strategy, such as GRH1, GRH2 and GRH3 (see Poldi et al. ^[13]). Note that the GRH used in the experimental tests in this paper refer to GRH1.

For Step 5, the remaining problem can be solved and made optimal by using some other method ^[29,30]. An integer linear optimization problem (considering the generation of all columns) can also be built to solve it. Such approaches, however, allow for overproduction, whereas the optimization problem studied in this paper does not allow for overproduction.

3.3.   Our algorithms

In this section, we fuse the VTC method with the FFD and greedy methods. Thus, two improved algorithms (i.e., Residual-VTC-FFD and Residual-VTC-Greedy, respectively) are obtained. The effectiveness of the VTC method is verified. More specifically, VTC can be used as described in Section 3.2.2 as a methodology for solving Step 2 and for Step 5. The definition of the residual problem, including its associated parameters, is assumed to be identical to that given in Section 3.2.2.

General framework of our approach:

Step 1: Let $c = 0$ and ${r^c} = d$ be the initial data for the original residual problem.

Step 2: Solve the relaxation solution to the residual equation problem by using the VTC technique in Section 3.1. Assume that the obtained objective function value f(x) ≤ K (K is defined as an LB of the current residual problem). If f(x) > K, the relaxation solution obtained by the column generation technique replaces the relaxation solution found via the VTC technique.

Step 3: Assume that the relaxation solution x is all nonnegative integers, and then stop. Otherwise, go to Step 4.

Step 4: Find an approximate integer solution ${\overline x ^c}$. If it is a null vector, go to Step 6.

Step 5: Update the demand for the residual problem, ${r^{c + 1}} = {r^c} - A{\overline x ^c}$. If ${r^c} = 0$, then stop. Otherwise, go to Step 2.

Step 6: Use the VTC and greedy methods to solve the remaining residual problems separately and choose the best solution as the final integer solution.

In Step 6, we prefer the side with the smallest objective function value as the final solution. If both have the same objective function value, the side with the lowest cutting patterns is chosen as the final solution. Our method differs from the residual heuristic in Steps 2 and 6. The good optimization capability of the column generation technique is exploited to compensate for the weak optimization capability of the VTC method. The quality of the solution can be improved. The cutting patterns (setups) can be reduced while obtaining a satisfactory material cost.

4.   Computational experiments

We used two different instances, one instance is from a previous study in the literature and the other is from an aluminum alloy factory in China. Benchmark instances are used to compare our algorithm with the published 1D-CSP algorithms. To solve the 1D-CSP model presented in this paper, there are six main published algorithms: FFD, greedy, residual-FFD, residual-greedy, residual-GRH and residual-BPP algorithms. These algorithms can be found in Cerqueira et al. ^[15] and Poldi et al. ^[13]. All experiments were implemented with Python 3.7 installed on a computer with an Intel Core i5-10400 processor at 2.90 GHz. The calculation time for each instance was limited to 20 s.

First set of instances: The 17 hard instances given by Wascher and Gau ^[29] are available at http://or.dei.unibo.it/library/bpplib.

Second set of instances: Foerster and Wäscher ^[31] used the problem generator CutGen1 to randomly generate a set of instances with 18 different classes.

Third set of instances: The authors collected 20 practical instances of making aluminum doors and windows in an aluminum alloy factory (see the Appendix).

4.1.   Results from the first set of instances

To test several algorithms on more challenging benchmarks, we tested 17 small-scale instances that were difficult to solve. These instances were designed by Wascher and Gau ^[29]. The stock object length L = 10,000, and the number of required items varies from 33 to 63. The majority of these items tend to have less demand. The minimum requirement of the item is only 1; thus, these instances can be used to estimate the performance of the constructive heuristic and our method. This is because the residual problem is a solution process for a lower-demand problem. For this set of instances, the number of iterations of our method was set to m, i.e., $\beta = 1$.

The results of three different methods are given in Table 1. The solution results of two well-known constructive heuristics and the proposed VTC technique are reported. Column 1 defines the name of the instances being tested, and the last column is the ideal optimal value of the objective function value. In the table, Obj represents the value of the objective function found, and N_P refers to the number of different cutting patterns (setups). The last line shows the sum of the counts for all instances.

The sum of the numbers of different cutting patterns for the VTC solution was significantly smaller than that for the other two methods. There is only one instance here, i.e., Waescher_TEST0084, where the N_P metric did not outperform the other two methods. This indicates that VTC is powerful in terms of simplifying setups (reducing the cutting patterns).

Comparing the FFD and greedy methods, the greedy method was best in terms of optimal objective function values, as opposed to our method, which was indistinguishable from FFD. For the Waescher_TEST0082 instance, our method obtained the same objective function value as the other methods. In this instance, a 12.0% reduction in pattern count could be obtained by using VTC instead of the greedy algorithm, and a 29.0% ( = 1-22/31) reduction in pattern count relative to FFD was observed. Relative to the greedy algorithm, the new solution reduced the number of patterns by a total of 20.8%, and a total of 29.3% relative to FFD.

4.2.   Results from the second set of instances

The second set consists of 18 classes of benchmark instances from Foerster and Wäscher ^[31]. There are 100 instances in each class, and we only tested the first 10 instances in each class. In accordance with Gau and Wäscher ^[32], the randomly generated instances could be the same as the original ones. The characteristics of the instances are shown in Table 2, where d denotes the number of item demands, d_r represents the average demand and m represents the number of item types. Different combinations of v₁ and v₂ were used to determine the size of items randomly generated in the interval [v₁L, v₂L]. The results of the calculation are shown in Table 3. Obj denotes the average of the number of stock objects used. N_P indicates the average number of cutting patterns. $\bar{LB}$ stands for the average of the ideal objective function values. Using Gap as the distance between the actual objective function value and the ideal solution (LB), we report it as a percentage:

Our objective function considered only the quantity of stock objects used, and the demand for each item type had to be met precisely, as in the mathematical model studied by Cerqueira et al. ^[15]. We tested the set of instances with each of the six representative mainstream algorithms, without considering the MGH method used by the authors in the literature. This is because the MGH method considered the results of two types of stock objects L₁ = 1000 and L₂ = 1001.

These 18 different types of instances can be divided into three groups, each containing six types of instances and having the same ${l_i}$ range (see Table 2). Specifically, Classes 1 to 6 were treated as Group 1, Classes 7 to 12 were treated as Group 2 and Classes 13 to 18 were treated as Group 3. The average pattern count and the average number of objects used count for each group of instances are reported in Tables 4 and 5, respectively. The algorithms shown in line 1 of Tables 4 and 5 correspond to all of the algorithms in Table 3. The fifth row in Tables 4 and 5 shows the average of the three previous sets of results. The last row in Table 4 represents the sum of the pattern counts for all instances in Table 3. The last row in Table 5 presents the sum of the stock objects used for all instances.

The six algorithmic solutions had a sum of material costs close to the LB (8892.4), whereas the other two constructive heuristics failed to reach optimality. The best performance in terms of material cost savings was the R-BPP algorithm. Our solution in terms of material cost was also closer to the LB. Remarkably, our method acquired the least number of cutting patterns compared to all other methods. This indicates that the algorithm (R-VTC-Greedy) developed can reduce cutting patterns.

Comparing R-VTC-Greedy and R-Greedy, the sum of the cutting pattern counts of the R-VTC-Greedy algorithm was smaller than that of the R-Greedy algorithm. As seen in Table 4, the total sum of pattern counts decreased by 3.95% ( = (1 - 423.3) / 440.7). On average, a 3.92% ( = (1 - 23.52) / 24.48) reduction in pattern counts could be achieved by the R-VTC-Greedy algorithm. This illustrates that the VTC method we developed can improve the solution quality of R-Greedy.

Comparing R-VTC-FDD and R-FDD, the sum of the cutting pattern counts of R-VTC-FDD was smaller than that of R-FDD. From the last row of Table 4, the sum of pattern counts solved by R-VTC-FDD was reduced by 3.28% ( = (1 - 429.3) / 443.9). On average, a 3.92% ( = (1 - 23.85) / 24.66) reduction in pattern counts could be achieved by R-VTC-FDD. This illustrates that the VTC method we developed can also improve the solution quality of R-FDD.

From the results for the set of instances, the reduction in cutting patterns was not very significant, mainly for two reasons. One is that the VTC algorithm developed by the authors currently has difficulty in obtaining fewer cutting patterns for a 1D-CSP with higher demands. The second is that the problem also leads to a reduction in the optimization capability of VTC when the demand is higher. This can be analyzed from the solution for the first set of instances and the solution for the third set of instances that follow.

In our methodology, the number of iterations was set to 2 m to solve this set of instances. We limited the computational time to 20 s for each instance, considering the effectiveness of the solution for instances with higher dimensionality.

4.3.   Results for the third set of instances

In the third set, there were 20 practical instances of industrial on-site processing. Tests on aluminum cutting were used to evaluate the performance of the best solutions generated by the new methodology for cost (material cost) minimization problems, as well as the usefulness of pattern reduction in practical cutting. Within a manufacturing plant, the objects in stock are 6000 cm in length. The engineering instances being solved at random were selected. These instances are provided in Table A.1 in the Appendix. For this set of instances, the number of iterations for our method was set to m, i.e., β = 2. In Table 6, the software Chuangying was developed by China Zibo Zhiying Network Technology Co., Ltd., which is a well-known and professional developer of door and window design and management software in China. The results of the calculated instances are exhibited in Table 6. To facilitate the analysis of the results, we set Obj to the number of objects used, and N_P is defined as the number of cutting patterns. Gap is the relative optimal gap, expressed as a percentage. N_p^VTC, N_p^FDD, N_p^Greedy, N_p^Chuangying, N_p^Residual-FFD, N_p^{Residual-Greedy}, N_p^Residual-GRH and N_p^{Residual-VTC-Greedy} represent the total numbers of cutting patterns produced by the different methods. As Table 6 shows, Residual-VTC-Greedy obtained a more satisfactory solution than several other similar mainstream algorithms.

The following data were obtained from the last row of the table:

They state that, by addressing the 1D-CSP model, the rate of improvement in the cutting pattern was 31.93% relative to Chuangying, 36.9% relative to FFD, 37.6% relative to the greedy algorithm, 35.8% relative to Residual-FFD, 33.1% relative to Residual-Greedy and 32.7% relative to Residual-GRH. Among the 20 instances reported, only instances 7_6000, 14_6000 and 18_6000 had cutting patterns that were not improved by our method. Closer inspection of the results shows that our method is effective not only in solving the original problem, but also in solving the remaining problems. For example, comparing the results for instances 8, 11, 13, 15, 19 and 20, when VTC failed to obtain the optimal objective function value, the cutting patterns could still be reduced in the solution to the residual problem at a later stage.

Figures 1 and 2 display the cutting patterns and their respective corresponding integer decision variables obtained by solving instance 1_6000 using our method and the commercial software, respectively. The symbol 1*6000*4 stands for the first cutting pattern produced and requires four objects to be cut according to that cutting pattern. The length of the object was 6000 cm. As can be seen from the graph, the two different methods solved for the same number of objects used, but our solution produced only four different cutting patterns, whereas the commercial software produced eight different cutting patterns, and the other methods in Table 6 produced even more cutting patterns.

5.   Conclusions and future works

In this paper, we reviewed some heuristics and column generation techniques from the literature. A new method called VTC has also been introduced and used to design two other new approaches for solving the integer 1D-CSP by successfully integrating it into two residual heuristics. In the first set of instances, the proposed VTC algorithm showed pattern reduction performance comparable to that of two well-known heuristics. In the second set of instances, a total of 100 well-known instances of different types were tested. The test results for the second set of instances showed an improvement of the average setup cost compared to several classical algorithms. In the third set of instances, 20 real-life instances were tested and the setup cost solved by the designed approaches was significantly less than that of the other published algorithms. In fact, in some practical applications, pattern reduction is essential to reduce the time cost of the setup and adjustment of machinery and equipment. Moreover, in practical applications, the demand needs to be met precisely (overproduction is not allowed), which helps to save material costs. We all know that overproduction tends to generate material waste.

This paper opens up new possibilities for future work. Efforts will be made to extend the VTC algorithm to address the 1D-CSP with multiple stock lengths and further pattern reduction in the future. In addition, the optimization capability and computational time of the new method can continue to be improved.

Acknowledgments

We are grateful for the incoming comments by the reviewers and editors, and we also appreciate the real data provided by Guangdong Weiye Aluminum Factory Co.

This work was supported in part by the Project of the National Key Research and Development Program of China (2021YFC1910402, 2022YFB4703103), National Natural Science Foundation of China (62073129, U21A20490, U22A2059) and Hunan Provincial Natural Science Foundation of China (2022JJ10020).

Conflict of interest

No potential conflict of interest has been reported by the authors.

Appendix