Comparative analysis of pattern-based models for the two-dimensional two-stage guillotine cutting stock problem. (September 2019)

• Record Type: Journal Article
• Authors: Kwon, Sue-Jeong; Joung, Seulgi; Lee, Kyungsik
• Is Part Of: Computers & operations research. Volume 109(2019)
• Page Start: 159
• Page End: 169
• Publication Date: 2019-09
• Subjects: Cutting stock problem -- Two-dimensional two-stage guillotine cuts -- Pattern-based models -- Comparative analysis; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2019.05.005
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: Pattern-based models for a two-dimensional two-stage guillotine cutting stock problem are analyzed and compared. A theoretical hierarchy of the strength of the lower bounds of the pattern-based models is formally established. Computational characteristics of the pattern-based models are also investigated and compared with benchmark instances. The staged-pattern models that have not been well-studied show competitive theoretical and computational performance. Abstract: This study presents a theoretical and computational analysis of integer programs based on the concept of the patterns, the so-called pattern-based models, for a two-dimensional two-stage guillotine cutting stock problem. The full-pattern models and the staged-pattern models with the corresponding column generation problems are analyzed and compared. Those pattern-based models have been actively used, however, their LP-relaxations have not been theoretically analyzed and compared. In this paper, we formally establish a hierarchy of the strength of lower bounds that can be obtained from their LP-relaxations. In addition, through computational tests with benchmark instances, we analyze the trade-off between the strength of the lower bounds and the required computation time to solve the LP-relaxations of the models. The quality of integer solutions obtained by an LP-based branch-and-bound algorithm with the columns generated during the process of solving the LP-relaxations of the models are also compared. The results show that one of the staged-pattern models, which has not been well-studied, shows competitive theoretical and computational performance.