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

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.

Keywords

• Integer programming
• Arc-flow formulation
• Strip cutting problem
• Graph compression.

References

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.