A polynomial mixed-integer linear programming model for two-dimensional guillotine strip packing problem

Document Type : Research Article

Author

Department of Mathematics, University of Science and Technology of Mazandaran, P.O. Box 4851878195, Behshahr, Iran

Abstract

A two-dimensional strip packing problem is the process of packing a set of rectangular items of given dimensions into a strip of bounded width and infinite height so that the used height of the strip is minimized. In the case that only guillotine packing is permitted, the problem is called the guillotine strip packing problem (GSPP). Guillotine packing commonly arises in different industries such as glass, steel, paper and wood. Nevertheless, there is a lack of explicit mathematical models for GSPP that can globally solve the problem. In this paper, a new mixed-integer programming model inspired by a so-called sequence sub-tour elimination technique for the traveling salesman problem (TSP) is presented as a relaxation of (non-staged) GSPP with orthogonal rotation. The proposed model is able to find good solutions (good upper bounds) for the optimal objective value and more importantly, it is a polynomial model of order $O(n^2)$, i.e. the number of decision variables (and constraints, as well) is a polynomial of order $O(n^2)$ in the number of the rectangular items ($n$). Numerical results show that the solutions obtained from the proposed model are superior to several existing heuristic algorithms in the literature.

Keywords

Main Subjects

References

[1] R. Alvarez-Valdes, F. Parreno, J. M. Tamarit, A tabu search algorithm for a two-dimensional non-
guillotine cutting problem, Eur. J. Oper. Res. 183 (2007) 1167–1182.
[2] B.S. Baker, E.G. Coffman Jr, R.L. Rivest, Orthogonal packing in two dimensions, SIAM J. Comput.
9 (1980) 846–855.
[3] M.A. Boschetti, A. Mingozzi, The two-dimensional finite bin packing problem. Part I: New lower
bounds for the oriented case, 4OR 1 (2003) 27–42.
[4] M.A. Boschetti, A. Mingozzi, The two-dimensional finite bin packing problem. Part II: New lower
and upper bounds, 4OR 1 (2003) 135–147.
[5] E.K. Burke, G. Kendall, G. Whitwell, A new placement heuristic for the orthogonal stock-cutting
problem, Oper. Res. 52 (2004) 655–671.
[6] P.M. Castro, I.E. Grossmann, From time representation in scheduling to the solution of strip packing
problems, Comput. Chem. Eng. 44 (2012) 45–57.
[7] P.M. Castro, J.F. Oliveira, Scheduling inspired models for two-dimensional packing problems, Eur.
J. Oper. Res. 215 (2011) 45–56.
[8] C.S. Chen, S. Sarin, R. Balasubramanian, A mixed-integer programming model for a class of as-
sortment problems, Eur. J. Oper. Res. 65 (1993) 362–367.
[9] H.I. Christensen, A. Khan, S. Pokutta, Approximation and online algorithms for multidimensional
bin packing: A survey, Comput. Sci. Rev. 24 (2017) 63–79.
[10] F. Furini, E. Malaguti, Models for the two-dimensional two-stage cutting stock problem with multi-
ple stock size, Comput. Oper. Res. 40 (2013) 1953–1962.
[11] F. Furini, E. Malaguti, R. M. Duran, A column generation heuristic for the two-dimensional two-
staged guillotine cutting stock problem with multiple stock size, Eur. J. Oper. Res. 218 (2012) 251–
260.
[12] F. Furini, E. Malaguti, D. Thomopulos, Modeling two-dimensional guillotine cutting problems via
integer programming, INFORMS J. Comput. 28 (2016) 736–751.
[13] Y.H. Huang, H.C. Lu, Y.C. Wang, Y.F. Chang, C.K. Gao, A global method for a two-dimensional
cutting stock problem in the manufacturing industry, in Application of Decision Science in Business
and Management, IntechOpen, 2020.
[14] M. Iori, V.L. de Lima, S. Martello, F.K. Miyazawa, M. Monaci, Exact solution techniques for two-
dimensional cutting and packing, Eur. J. Oper. Res. 289 (2021) 399–415.
[15] M. Iori, S. Martello, M. Monaci, Metaheuristic Algorithms for the Strip Packing Problem, US:
Springer, 2003.
[16] T.W. Leung, C.K. Chan, M.D. Troutt, Application of a mixed simulated annealing-genetic algo-
rithm for a 2D packing problem, Eur. J. Oper. Res. 145 (2003) 530–542.
[17] H.L. Li, C.T. Chang, An approximately global optimization method for assortment problems, Eur.
J. Oper. Res. 105 (1998) 604–612.
[18] A. Lodi, S. Martello, D. Vigo, Models and bounds for two-dimensional level packing problems, J.
Comb. Optim. 8 (2004) 363–379.
[19] A. Lodi, M. Monaci, Integer linear programming models for 2-staged two-dimensional knapsack
problems, Math. Program. 94 (2003) 257–278.
[20] R. Macedo, C. Alves, J.M. Valerio de Carvalho, Arc-flow model for the two-dimensional guillotine
cutting stock problem, Comput. Oper. Res. 37 (2010) 991–1001.
[21] S. Martello, M. Monaci, D. Vigo, An exact approach to the strip-packing problem, INFORMS J.
Comput. 15 (2003) 310–319.
[22] M. Martin, R. Morabito, P. Munari, A bottom-up packing approach for modeling the constrained
two-dimensional guillotine placement problem, Comput. Oper. Res. 115 (2020) 104851.
[23] S.B. Messaoud, C. Chu, M.L. Espinouse, Characterization and modelling of guillotine constraints,
Eur. J. Oper. Res. 191 (2008) 112–126.
[24] C. Miller, A. Tucker, R. Zemlin, Integer programming formulations and travelling salesman prob-
lems, J. ACM 7 (1960) 326–329.
[25] M. Monaci, P. Toth, A set-covering-based heuristic approach for bin-packing problems, INFORMS
J. Comput. 18 (2006) 71–85.
[26] M. Mrad, An arc flow-based optimization approach for the two-stage guillotine strip cutting prob-
lem, J. Oper. Res. Soc. 66 (2015) 1850–1859.
[27] N. Ntene, J. van Vuuren, A survey and comparison of guillotine heuristics for the 2D oriented offline
strip packing problem, Discrete Optim. 6 (2009) 174–188.
[28] F. Parreno, R. Alvarez-Valdes, J.F. Oliveira, J.M. Tamarit, A hybrid GRASP/VND algorithm for
two- and three-dimensional bin packing, Ann. Oper. Res. 179 (2010) 203–220.
[29] J. Puchinger, G.R. Raidl, Models and algorithms for three-stage two-dimensional bin packing, Eur.
J. Oper. Res. 183 (2007) 1304–1327.
[30] C.D. Rodrigues, A.C. Cherri, S.A. de Araujo, Strip based compact formulation for two-dimensional
guillotine cutting problems, Comput. Oper. Res. 149 (2023) 106044.
[31] S.M. Shperling, Y.A. Kochetov, A knapsack problem for rectangles under center-of-gravity con-
straints, J. Appl. Ind. Math. 16 (2022) 563–571.
[32] E. Silva, F. Alvelos, J.M. Valerio de Carvalho, An integer programming model for two- and three-
stage two-dimensional cutting stock problems, Eur. J. Oper. Res. 205 (2010) 699–708.
[33] L. Wei, H. Qin, B. Cheang, X. Xu, An efficient intelligent search algorithm for the two-dimensional
rectangular strip packing problem, Int. Trans. Oper. Res. 23 (2016) 65–92.
Journal of Mathematical Modeling
Volume 13, Issue 2
May 2025
Pages 415-428

Files

Share

How to cite

Statistics