An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems
Introduction
The two-dimensional cutting problem (2DCP) consists in dissecting a large rectangular object (stock sheet) in small rectangles (pieces) with the aim of minimizing the trim loss or maximizing the profit associated to the extracted pieces. The guillotine variant of the 2DCP uses just straight cuts dissecting a rectangle in two parts. When the number of pieces to be extracted is unbounded, then the problem is referred to as the unconstrained two-dimensional guillotine cutting problem (U2DCP), otherwise it is referred to as constrained (C2DCP).
The 2DCP has been widely treated in the literature by exact (dynamic programming, branch and bound, MIP models) and heuristic approaches as witnessed by the survey papers of Dyckhoff et al. [7], Lodi et al. [14] and Wäscher et al. [18].
Gilmore and Gomory [10] introduced the 2DCP and proposed two dynamic programming procedures based on the knapsack function. Herz [12] and Christofides and Withlock [3] proposed the first approaches introducing the so-called discretization points (also known as normal coordinates). The ideas proposed in these works have been widely explored in the literature. Concerning the dynamic programming, one of the main reasons of the research interest in this approach is that it returns the optimal solution for all the U2DC subproblems related to the subrectangles included in the sheet. These solutions are generally used as upper bounds in the C2DCP. Concerning instead the discretization points, they allow to reduce the problem size and consequently the computational effort. For this reason some contributions presented new performing methods for the computation and the reduction of the discretization points.
In this perspective Beasley [1] was the first one proposing an exact and a heuristic algorithm complementing the basic Gilmore and Gomory [10] dynamic programming procedure with the discretization points. In particular, in the heuristic algorithm, the author finds a suboptimal solution using a subset of the discretization points obtained through the iterative elimination of the smallest pieces, until a prefixed size of the subset is achieved.
Scheithauer and Terno [17] introduced the raster points, which constitute a subset of the discretization points. The raster points, contrarily to the subset proposed by Beasley [1], can be used in an exact dynamic programming algorithm without loss of optimality.
Cintra et al. [4], working on the idea of Beasley [1], proposed an exact dynamic programming procedure which simplifies the computation of the knapsack function and presented efficient procedures for the computation of the discretization points. Moreover, they reduced the number of the discretization points introducing an idea which partially recalls the raster points.
Kang and Yoon [13] proposed a branch and bound algorithm which is the best exact algorithm in the literature for the U2DCP. They modified the algorithm of Young-Gun et al. [19] improving the upper bound and using anti-redundancy and dominance techniques, based on the development of the strategies proposed in Cung et al. [6]. Moreover they introduced a pre-processing to be performed before running the algorithm aimed at reducing the number of piece types to be taken into account. This pre-processing is independent from the solving approach.
Recently Birgin et al. [2] proposed a two-phase heuristic for the non-guillotine case of U2DCP, which in the first phase solves the guillotine variant of the problem. This phase has two steps: a fast heuristic step based on the two-stage algorithm by Gilmore and Gomory [9] and an exact dynamic programming step. They used the raster points and introduced a pre-processing similar to the one of Kang and Yoon [13], but less performing even if faster. For very large size instances they obtained good suboptimal solutions, using a subset of the raster points.
Russo et al. [16] corrected and improved one of the two dynamic programming procedures by Gilmore and Gomory [10]. Moreover they introduced in their algorithm the reduction of the discretization points proposed by Cintra et al. [4], and a pre-processing which modifies the one proposed by Birgin et al. [2]. To the best of our knowledge, this algorithm is the best exact dynamic programming algorithm proposed in the literature for the U2DCP.
The main weakness point of the exact approaches, and in particular of the dynamic programming algorithms, resides in the large memory requirements.
In this work we propose five improvements which allow to overcome these limits. In particular the first two improvements are derived from ideas present in the literature, i.e. the raster points and the pre-processing on piece types. Concerning the raster points, we provide an efficient data structure for their integrations whereas, concerning the pre-processing, we propose new effective strategies. It is important to underline that both these improvements can be used regardless of the adopted solving approach. The remaining three improvements are strongly correlated and are specifically referred to knapsack function based algorithms and in particular to the one by Russo et al. [16]. These improvements, based on proofed theoretical results, allow to significantly reduce the solution space of the algorithm, avoiding redundant solutions without loss of the feasible ones.
All these enhancements, together with several computational refinements are integrated in a new dynamic programming algorithm, which modifies the one by Russo et al. [16]. The proposed algorithm significantly outperforms the best available solving approaches present in the literature for the U2DCP and determines the optimal solution of unsolved very large size instances.
The paper is structured as follows. In Section 2 we recall the U2DCP setting, the knapsack function and the algorithm by Russo et al. [16]. In Section 3 we describe the proposed improvements. Section 4 presents the new algorithm and provides also some computer programming refinements. Finally Section 5 presents a computational study of the proposed improvements and the results obtained on literature instances.
Section snippets
Unconstrained cutting problem and knapsack function
In the U2DCP a single large rectangular stock sheet of dimensions L and W has to be dissected in order to obtain smaller rectangular pieces among n given types {t1, t2,…, tn}, each of them characterized by its dimensions (li, wi) and profit πi. Pieces are extracted from the sheet, without overlapping, by a sequence of vertical and horizontal straight guillotine cuts, i.e. cuts which divide a rectangle into two parts. No piece rotation is allowed.
A set of guillotine cuts is referred to as
Modifications and enhancements of the RS_kf algorithm
As said above the main limit of the U2DCP solving approaches and in particular of the ones based on the knapsack function is in the high memory required to allocate large size matrices: f, f0′, fv, fh, λ, ω. In the following subsections we propose five modifications of RS_kf which have the twofold aim of reducing the memory allocation and speeding up the algorithm:
- i
integration of the raster points;
- ii
two-step pre-processing;
- iii
modification of the one-piece term;
- iv
λ and ω reduction;
- v
inner and outer cycles
The revised RS_kf algorithm
In this section we present the revised RS_kf algorithm, referred to as RS_kf2, where we introduced all the improvements proposed in Section 3. We explain the pseudocode without taking into account the raster points and then we briefly discuss the details of their integration. This section concludes with the proposal of further memory reduction refinements.
Computational experiments
In this section we report the computational results obtained on large and very large size U2DCP instances present in literature. With reference to Russo et al. [16], we consider the six large weighted and unweighted instances with the highest computation time. The six weighted instances are APT20, APT22, APT24, APT28, APT29 and W4. These instances belong to the OR library PackLib2 by Fekete and van der Veen [8]. The six unweighted instances are B7 by Cui et al. [5], gcut16, gcut16r, gcut17 and
Conclusions
In this paper we tackled the unconstrained two dimensional cutting problem (U2DCP), proposing a new dynamic programming algorithm which enhances the exact algorithm by Russo et al. [16]. In particular the algorithm at first performs an original pre-processing in order to reduce the number of pieces to be taken into account. Then it implements a new definition of the knapsack function and of the λ and ω support functions. Finally several proofed original conditions are introduced in order to
References (19)
- et al.
Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation
Eur J Oper Res.
(2008) - et al.
PackLib2: an integrated library of multi-dimensional packing problems
Eur J Oper Res
(2007) - et al.
Two-dimensional packing problems: a survey
Eur J Oper Res
(2002) - et al.
An improvement of the knapsack function based algorithm of Gilmore and Gomory for the unconstrained two-dimensional guillotine cutting problem
Int J Prod Econ, Special Issue on Cutting and Packing
(2013) - et al.
An improved typology of cutting and packing problems
Eur J Oper Res
(2007) Algorithms for unconstrained two-dimensional guillotine cutting
J Oper Res Soc
(1985)- et al.
Generating unconstrained two-dimensional non guillotine cutting patterns by a recursive partitioning algorithm
J Oper Res Soc
(2012) - et al.
An algorithm for two-dimensional cutting problems
Oper Res
(1977) - et al.
Exact and heuristic algorithms for staged cutting problems
Proc Inst Mech Eng, Part B: J Eng Manuf
(2005)
Cited by (24)
Improved dynamic programming algorithms for unconstrained two-dimensional guillotine cutting
2024, Computers and Operations ResearchExact approaches for the unconstrained two-dimensional cutting problem with defects
2023, Computers and Operations ResearchStrip based compact formulation for two-dimensional guillotine cutting problems
2023, Computers and Operations ResearchThe Floating-Cuts model: a general and flexible mixed-integer programming model for non-guillotine and guillotine rectangular cutting problems
2023, Omega (United Kingdom)Citation Excerpt :The authors considered a hybrid strategy combining a depth search heuristic and hill climbing to search the graph. Cintra et al. [8] and Russo et al. [42,43] considered a dynamic programming procedure for the unbounded case. Cintra et al. [8] used algorithms based on dynamic programming to solve the 2DSLOPP with different variants allowing the rotation of orthogonal items, k-staged patterns, and non-staged patterns.
Exact solution techniques for two-dimensional cutting and packing
2021, European Journal of Operational Research