Click on the links below to download the benchmark instances used in the following papers:

-

Martin, M.; Morabito, R.; Munari, P. A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem. Computers & Operations Research, v. 115, 104851, 2020.

Abstract: In this paper, we address the Constrained Two-dimensional Guillotine Placement Problem (C2GPP). This problem considers a rectangular large object and a set of rectangular small item types of given sizes and values. The objective is to select and cut the most valuable subset of small items from the large object using orthogonal guillotine cuts and constrained patterns. To completely model the problem, we present pseudo-polynomial and compact integer non-linear formulations. Then, we obtain an equivalent Mixed Integer Linear Programming (MILP) formulation from each non-linear model. These novel formulations are related to a bottom-up packing approach of successive horizontal and vertical builds of the small items. Additionally, we develop a set of constraints for each model which allows us to strictly consider d-staged guillotine cutting patterns, for a given positive integer d. To evaluate the MILP models and compare their performance to the state-of-the-art formulation of the C2GPP, we run computational experiments using three sets of benchmark instances, two of them from the literature. The results show that the proposed models, based on a bottom-up packing approach, lead to optimal or near-optimal solutions in reasonable processing times, even for scenarios that are intractable for the benchmark model.

[Instances] [Full paper]

-

Martin, M.; Hokama, P.; Morabito, R.; Munari, P. The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation, a Benders decomposition and a CP-based algorithm. International Journal of Production Research, v. 58 (9), p. 2712-2729, 2020.

Abstract: This paper addresses a variant of two-dimensional cutting problems in which rectangular small pieces are obtained by cutting a rectangular object through guillotine cuts. The characteristics of this variant are: (i) the object contains some defects, and the items cut must be defective-free; (ii) there is an upper bound on the number of times an item type may appear in the cutting pattern (constrained case); (iii) there is no limitation on the number of guillotine stages (stage-unrestricted case). This problem commonly arises in industrial settings that deal with defective materials, e.g., either by intrinsic characteristics of the object as in the cutting of wooden boards with knotholes in the wood industry, or by the manufacturing process as in the production of flat glass in the glass industry. Despite its potential applicability, few studies in the literature have addressed cutting problems with defective materials. Indeed, to the best of our knowledge, there is no approach in the literature with computational experiments for the present constrained two-dimensional guillotine case. We propose a compact integer linear programming (ILP) model for this problem based on the discretization of the defective object. As solution methods for the problem, we develop a Benders decomposition algorithm and a constraint-programming (CP) based algorithm. We evaluate these approaches through computational experiments, using benchmark instances from the literature. The results show that the methods are effective on different types of instances and can find optimal solutions even for instances with dimensions close to real-size. They also indicate that the performance of the proposed approaches improves as the number of defects increases, in contrast to other approaches from the literature.

[Instances] [Full paper]