Column generation approach for 1.5-dimensional cutting stock problem with technical constraints

Year 2024, , 335 - 350, 30.09.2024

Müjgan Sağır , Tuğba Saraç

https://doi.org/10.53391/mmnsa.1492749

Abstract

In this study, the 1.5-dimensional cutting stock problem with technical constraints is considered. In the literature, this problem is also defined as a strip packing or open dimension problem. When given a strip of infinite length and bounded width, the problem is to define a packing of rectangular objects into a strip that minimizes its final length. Technical constraints, such as the order type and the number of strips, are indispensable in real life; however, they are often neglected in the literature because they make the problem difficult to solve. Only one study was reached in the literature that took into account technical constraints, but in that mentioned study, only a mathematical model was proposed for the problem. In this context, our aim is to solve the problem with a more effective approach. The research question in this study is the usability of the column generation technique to solve the 1.5-dimensional cutting stock problem. In this study, the column generation approach was proposed for the first time for the considered problem. To demonstrate the performance of the proposed solution method, randomly generated test problems were solved with GAMS/Cplex. As we report the results, proposed column generation approach (CG) reaches very close (such as %1 and %2 error) solutions to integrated mathematical model (IM) for small sized problems in a second. On the other hand, while CG solved all the problems in a reasonable time, IM could not produce a feasible solution to some problems. Numerical experiments showed that the column generation algorithm outperforms the integrated mathematical model for the problem.

Keywords

1.5-dimensional cutting problem, column generation, mixed-integer linear programming

References

• [1] Dyckhoff, H., Kruse, H.J., Abel, D. and Gal, T. Trim loss and related problems. Omega, 13(1), 59-72, (1985).
• [2] Adakçı, S. Stok Kesme Problemi: Alüminyum Sektöründe Uygulaması. Yüksek Lisans Tezi, İstanbul Teknik Üniversitesi Fen Bilimleri Enstitüsü, İstanbul, (2001).
• [3] Dyckhoff, H. A typology of cutting and packing problems. European Journal of Operational Research, 44(2), 145-159, (1990).
• [4] Song, X., Chu, C.B., Nie, Y.Y. and Bennell, J.A. An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem. European Journal of Operational Research, 175(3), 1870-1889, (2006).
• [5] Saraç, T. and Özdemir, M.S. A genetic algorithm for 1.5 dimensional assortment problems with multiple objectives. In Proceedings, International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems (IEA/AIE), pp. 41-51, Heidelberg, Berlin, (2003, June).
• [6] Gasimov, R.N., Sipahioglu, A. and Saraç, T. A multi-objective programming approach to 1.5-dimensional assortment problem. European Journal of Operational Research, 179(1), 64-79, (2007).
• [7] Kokten, E.S. and Sel, Ç. A cutting stock problem in the wood products industry: a two-stage solution approach. International Transactions in Operational Research, 29(2), 879-907, (2022).
• [8] Saraç, T. and Sa˘gır, M. Mixed-Integer programming models for 1.5-dimensional cutting problem with technical constraints. Journal of the Faculty of Engineering and Architecture of Gazi University, 36(1), 291-302, (2021).
• [9] Duysak, E., Dülger, ˙I., Yıldız, N.S., Gümü¸s, S. and Saraç, T. Teslim zamanlarinin dikkate alındı˘gı 1,5 boyutlu kesme Ve ana malzeme seçimi problemi için bir matsezgisel algoritma. Endüstri Mühendisli˘gi, 33(2), 402-412, (2022).
• [10] Vasilyev, I., Ushakov, A.V., Zhang, D. and Ren, J. Generalized multiple strip packing problem: Formulations, applications, and solution algorithms. Computers & Industrial Engineering, 178, 109096, (2023).
• [11] Liu, K., Zhang, H., Wang, C., Li, H., Chen, Y. and Chen, Q. Robust optimization for the two-dimensional strip-packing problem with variable-sized bins. Mathematics, 11(23), 4781, (2023).
• [12] Bezerra, V.M.R., Leao, A.A.S., Oliveira, J.F. and Santos, M.O. Models for the two-dimensional level strip packing problem-a review and a computational evaluation. Journal of the Operational Research Society, 71(4), 606–627, (2020).
• [13] Wäscher, G., Haußner, H. and Schumann, H. An improved typology of cutting and packing problems. European Journal of Operational Research, 183(3), 1109-1130, (2007).
• [14] Sugi, M., Shiomi, Y., Okubo, T., Nagai, H., Inoue, K. and Ota, J. Solution of the rectangular strip packing problem considering a 3-stage guillotine cutting constraint with finite slitter blades. International Journal of Automation Technology, 14(3), 447-458, (2020).
• [15] Cintra, G.F., Miyazawa, F.K., Wakabayashi, Y. and Xavier, E.C. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. European Journal of Operational Research, 191(1), 61-85, (2008).
• [16] Bettinelli, A., Ceselli, A. and Righini, G. A branch-and-price algorithm for the twodimensional level strip packing problem. 4OR, 6, 361-374, (2008).
• [17] Cui, Y.P., Zhou, Y. and Cui, Y. Triple-solution approach for the strip packing problem with two-staged patterns. Journal of Combinatorial Optimization, 34, 588-604, (2017).
• [18] Bertoli, F., Kilby, P. and Urli, T. A column-generation-based approach to fleet design problems mixing owned and hired vehicles. International Transactions in Operational Research, 27(2), 899-923, (2020).
• [19] Kamran, M.A., Karimi, B. and Dellaert, N. A column-generation-heuristic-based benders’ decomposition for solving adaptive allocation scheduling of patients in operating rooms. Computers & Industrial Engineering, 148, 106698, (2020).
• [20] Faiz, T.I., Vogiatzis, C. and Noor-E-Alam, M. A column generation algorithm for vehicle scheduling and routing problems. Computers & Industrial Engineering, 130, 222-236, (2019).
• [21] Changchun, L., Xi, X., Canrong, Z., Qiang, W. and Li, Z. A column generation based distributed scheduling algorithm for multi-mode resource constrained project scheduling problem. Computers & Industrial Engineering, 125, 258-278, (2018).
• [22] Kasimbeyli, N., Saraç, T. and Kasimbeyli, R. A two-objective mathematical model without cutting patterns for one-dimensional assortment problems. Journal of Computational and Applied Mathematics, 235(16), 4663-4674, (2011).