Comparative analysis of mathematical formulations for the two‐dimensional guillotine cutting problem
- 3 August 2023
- journal article
- research article
- Published by Wiley in International Transactions in Operational Research
- Vol. 31 (5) , 3010-3035
Abstract
About 15 years ago, a paper proposed the first integer linear programming formulation for the constrained two‐dimensional guillotine cutting problem (with unlimited cutting stages). Since then, eight other formulations followed, seven of them in the last four years. This spike of interest gave no opportunity for a comprehensive comparison between the formulations. We review each formulation and compare their empirical results over instance datasets of the literature. We adapt most formulations to allow for piece rotation. The possibility of adaptation was already predicted but not realized by the prior work. The results show the dominance of pseudo‐polynomial formulations until the point instances become intractable by them, while more compact formulations keep achieving good primal solutions. Our study also reveals a mistake in the generation of the T instances, which should have the same optima with or without guillotine cuts. We also propose hybridising a recent formulation with a prior formulation for a restricted version of the problem. The hybridisations show a reduction of about 20% of the branch‐and‐bound time thanks to the symmetries broken by the hybridisation.Keywords
All Related Versions
Funding Information
- Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (001)
- Fundação de Amparo à Pesquisa do Estado de São Paulo (2016/01860‐1, 2022/05803‐3)
This publication has 49 references indexed in Scilit:
- A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraintAnnals of Operations Research, 2012
- Arc-flow model for the two-dimensional guillotine cutting stock problemComputers & Operations Research, 2010
- Characterization and modelling of guillotine constraintsEuropean Journal of Operational Research, 2008
- Integer linear programming models for 2-staged two-dimensional Knapsack problemsMathematical Programming, 2003
- Constrained two‐dimensional cutting stock problems a best‐first branch‐and‐bound algorithmInternational Transactions in Operational Research, 2000
- An efficient approach for large-scale two-dimensional guillotine cutting stock problemsJournal of the Operational Research Society, 1998
- Constrained two-dimensional cutting: an improvement of Christofides and Whitlock's exact algorithmJournal of the Operational Research Society, 1997
- An exact algorithm for orthogonal 2-D cutting problems using guillotine cutsEuropean Journal of Operational Research, 1995
- A computational improvement to Wang's two-dimensional cutting stock algorithmComputers & Industrial Engineering, 1989
- Algorithms for Unconstrained Two-Dimensional Guillotine CuttingJournal of the Operational Research Society, 1985