Column generation approach for 1.5-dimensional cutting stock problem with technical constraints
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).