A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem

• Published in: Computers & operations research 2020-03, Vol.115, p.104851, Article 104851
• Main Authors: Martin, Mateus, Morabito, Reinaldo, Munari, Pedro
• Format: Article
• Language: English
• Subjects: Benchmarks; Bottom-up packing; Constrained two-dimensional cutting; Constraint modelling; Cutting & packing problems; Integer programming; Linear programming; Mixed integer; Mixed integer linear programming; Non-staged and staged guillotine cuts; Operations research; Placement; Polynomials; Two dimensional models
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2019.104851

•We address the constrained two-dimensional guillotine placement problem.•We present novel pseudo-polynomial and compact integer non-linear formulations.•Equivalent integer linear formulations from the non-linear models are proposed.•We run computational experiments using different sets of benchmark instances.•Optimal or near-optimal solutions are obtained in reasonable processing times. 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.