SavedAdd your journal

Journals / The Eurasia Proceedings of Educational and Social Sciences / 2026 / Volume: 22

The Two-Dimensional Strip Cutting Problem: Improved Results on Real-World Instances

Mehdi Mrad(King Saud University)
Tamer G. Alı(King Saud University)
Ali Balma(Ecole Nationale Supérieure d’Ingénieurs de Tunis)
Anis Gharbı(King Saud University)
Ali Samhan(King Saud University)
M. A. Louly(Ecole Supérieure Polytechnique Mauritanie)
Pages
—
Publication Date
2021-12-31
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

A graph compression method is proposed and it is shown that substantially better results are achieved in obtaining optimal or near-optimal solutions of real-world instances.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:Cutting and packing problems arise in various industrial settings such as production of metal, glass sheets, papers, etc.
📊
Key Findings & Data:Each item i (i=1,2,…,m) has a width wi, a height hi, and a demand di.
💡
Conclusion & Impact:A graph compression method is proposed and it is shown that substantially better results are achieved in obtaining optimal or near-optimal solutions of real-world instances.
🔬Design:Conference Paper
📍Scope:Comprehensive Sample
⚙️Variables:Integer programming · Arc-flow formulation · Strip cutting problem

Abstract

Cutting and packing problems arise in various industrial settings such as production of metal, glass sheets, papers, etc. The demand of items should be met while minimizing loss of waste material. One of the most known as a contemporary problem in field of operations research is the two-dimensional strip cutting problem. A set of m rectangular items is to be cut from a two-dimensional strip of width W and infinite height. Each item i (i=1,2,…,m) has a width wi, a height hi, and a demand di. The objective is to determine how to cut the demanded items using the minimum height of strip and meet all the demands, while respecting the two stages of guillotine cuts. We address the arc-flow formulation for this NP-hard problem. A graph compression method is proposed and it is shown that substantially better results are achieved in obtaining optimal or near-optimal solutions of real-world instances.

🔖

Cite This Article

Mrad, M., Alı, T. G., Balma, A., Gharbı, A., Samhan, A., Louly, M. A. (2021). The Two-Dimensional Strip Cutting Problem: Improved Results on Real-World Instances. The Eurasia Proceedings of Educational and Social Sciences, Volume: 22. https://doi.org/10.55549/epess.1040517

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (12)

  1. Brandão, Filipe, and João Pedro Pedroso. 2016. “Bin Packing and Related Problems: General Arc-Flow Formulation with Graph Compression.” Computers and Operations Research 69: 56–67. http://dx.doi.org/10.1016/j.cor.2015.11.009.
  2. Delorme, Maxence, Manuel Iori, and Silvano Martello. 2016. “Bin Packing and Cutting Stock Problems: Mathematical Models and Exact Algorithms.” European Journal of Operational Research 255(1): 1–20. http://dx.doi.org/10.1016/j.ejor.2016.04.030.
  3. Dyckhoff, Harald. 1990. “A Typology of Cutting and Packing Problems.” European Journal of Operational Research 44(2): 145–59.
  4. Hifi, Mhand. 1998. “Exact Algorithms for the Guillotine Strip Cutting/Packing Problem.” Computers and Operations Research 25(11): 925–40.
  5. Iori, Manuel et al. 2021. “Exact Solution Techniques for Two-Dimensional Cutting and Packing.” European Journal of Operational Research 289(2): 399–415. https://doi.org/10.1016/j.ejor.2020.06.050.
  6. Lodi, Andrea, Silvano Martello, and Daniele Vigo. 1999. “Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems.” INFORMS Journal on Computing 11(4): 345–57.
  7. Lodi, Andrea, and Michele Monaci. 2003. “Integer Linear Programming Models for 2-Staged Two-Dimensional Knapsack Problems.” Mathematical Programming, Series B 94(2–3): 257–78.
  8. Macedo, Rita, Cláudio Alves, and J. M. Valério de Carvalho. 2010. “Arc-Flow Model for the Two-Dimensional Guillotine Cutting Stock Problem.” Computers and Operations Research 37(6): 991–1001. http://dx.doi.org/10.1016/j.cor.2009.08.005.
  9. Martinovic, J., G. Scheithauer, and J. M. Valério de Carvalho. 2018. “A Comparative Study of the Arcflow Model and the One-Cut Model for One-Dimensional Cutting Stock Problems.” European Journal of Operational Research 266(2): 458–71.
  10. Mrad, M., I. Meftahi, and M. Haouari. 2013. “A Branch-and-Price Algorithm for the Two-Stage Guillotine Cutting Stock Problem.” Journal of the Operational Research Society 64(5): 629–37. http://dx.doi.org/10.1057/jors.2012.70.
  11. Mrad, Mehdi. 2015. “An Arc Flow-Based Optimization Approach for the Two-Stage Guillotine Strip Cutting Problem.” Journal of the Operational Research Society 66(11): 1850–59.
  12. Wäscher, Gerhard, Heike Haußner, and Holger Schumann. 2007. “An Improved Typology of Cutting and Packing Problems.” European Journal of Operational Research 183(3): 1109–30.