The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation, a Benders decomposition and a CP-based algorithm

References

• Afsharian, M., A. Niknejad, and G. Wäscher. 2014. “A Heuristic, Dynamic Programming-based Approach for a Two-dimensional Cutting Problem with Defects.” OR Spectrum 36 (4): 971–999. doi:10.1007/s00291-014-0363-x.
   Web of Science ®Google Scholar
• Beasley, J. E. 1985a. “Algorithms for Unconstrained Two-Dimensional Guillotine Cutting.” The Journal of the Operational Research Society 36 (4): 297–306. doi:10.2307/2582416. http://www.jstor.org/stable/2582416?origin=crossref.
   Web of Science ®Google Scholar
• Beasley, J. E. 1985b. “An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure.” Operations Research 33 (1): 49–64. doi:10.1287/opre.33.1.49.
   Web of Science ®Google Scholar
• Ben Messaoud, S., C. Chu, and M. L. Espinouse. 2008. “Characterization and Modelling of Guillotine Constraints.” European Journal of Operational Research 191 (1): 112–126. doi:10.1016/j.ejor.2007.08.029.
   Web of Science ®Google Scholar
• Carnieri, C., G. A. Mendoza, and W. G. Luppold. 1993. “Optimal Cutting of Dimension Parts From Lumber with a Defect.” Forest Produts Journal 43: 66–72.
   Web of Science ®Google Scholar
• Christofides, N., and C. Whitlock. 1977. “An Algorithm for Two-Dimensional Cutting Problems.” Operations Research 25 (1): 30–44. doi:10.1287/opre.25.1.30.
   Web of Science ®Google Scholar
• Cintra, G. F., F. K. Miyazawa, Y Wakabayashi, and E. C. Xavier. 2008. “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. doi:10.1016/j.ejor.2007.08.007.
   Web of Science ®Google Scholar
• Delorme, M., M. Iori, and S. Martello. 2017. “Logic Based Benders' Decomposition for Orthogonal Stock Cutting Problems.” Computers & Operations Research 78: 290–298. doi:https://doi.org/10.1016/j.cor.2016.09.009. http://www.sciencedirect.com/science/article/pii/S0305054816302301.
   Web of Science ®Google Scholar
• Dolatabadi, M., A. Lodi, and M. Monaci. 2012. “Exact Algorithms for the Two-dimensional Guillotine Knapsack.” Computers and Operations Research 39 (1): 48–53. doi:10.1016/j.cor.2010.12.018.
   Web of Science ®Google Scholar
• Durak, B., and D. T. Aksu. 2017. “Dynamic Programming and Mixed Integer Programming Based Algorithms for the Online Glass Cutting Problem with Defects and Production Targets.” International Journal of Production Research 55 (24): 7398–7411. doi:10.1080/00207543.2017.1349951.
   Web of Science ®Google Scholar
• Furini, F., E. Malaguti, and D. Thomopulos. 2016. “Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming.” INFORMS Journal on Computing 28 (4): 736–751. doi:10.1287/ijoc.2016.0710.
   Web of Science ®Google Scholar
• Gilmore, P. C., and R. E. Gomory. 1961. “A Linear Programming Approach to the Cutting-Stock Problem.” Operations Research 9 (6): 849–859. doi:10.1287/opre.9.6.849.
   Web of Science ®Google Scholar
• Gilmore, P. C., and R. E. Gomory. 1963. “A Linear Programming Approach to the Cutting Stock Problem: Part II.” Operations Research 11 (6): 863–888. doi:10.1287/opre.11.6.863.
   Web of Science ®Google Scholar
• Gilmore, P. C., and R. E. Gomory. 1965. “Multistage Cutting Stock Problems of Two and More Dimensions.” Operations Research 13 (1): 94–120. doi:10.1287/opre.13.1.94.
   Web of Science ®Google Scholar
• Gilmore, P. C., and R. E. Gomory. 1966. “The Theory and Computation of Knapsack Functions.” Operations Research 14 (6): 1045–1074. doi:10.1287/opre.14.6.1045.
   Web of Science ®Google Scholar
• Hahn, S. G. 1968. “On the Optimal Cutting of Defective Sheets.” Operations Research 16 (6): 1100–1114. doi:10.1287/opre.16.6.1100.
   Web of Science ®Google Scholar
• Herz, J. C. 1972. “Recursive Computational Procedure for Two-dimensional Stock Cutting.” IBM Journal of Research and Development 16 (5): 462–469. doi:10.1147/rd.165.0462.
   Web of Science ®Google Scholar
• Lodi, A., S. Martello, and M. Monaci. 2002. “Two-dimensional Packing Problems: A Survey.” European Journal of Operational Research 141 (2): 241–252. doi:10.1016/S0377-2217(02)00123-6.
   Web of Science ®Google Scholar
• Morabito, R., and V. Pureza. 2010. “A Heuristic Approach Based on Dynamic Programming and/or-graph Search for the Constrained Two-dimensional Guillotine Cutting Problem.” Annals of Operations Research 179 (1): 297–315. doi:10.1007/s10479-008-0457-4.
   Web of Science ®Google Scholar
• Neidlein, V., A. Scholz, and G. Wäscher. 2016. “SLOPPGEN: A Problem Generator for the Two-dimensional Rectangular Single Large Object Placement Problem with Defects.” International Transactions in Operational Research 23 (1–2): 173–186. doi:10.1111/itor.12119.
   Web of Science ®Google Scholar
• Neidlein, V., A. C. G. Vianna, M. N. Arenales, and G. Wäscher. 2008. The Two-Dimensional, Rectangular, Guillotineable-Layout Cutting Problem with a Single Defect. FEMM Working Papers 08035, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management. https://ideas.repec.org/p/mag/wpaper/08035.html.
   Google Scholar
• Pisinger, D., and M. Sigurd. 2007. “Using Decomposition Techniques and Constraint Programming for Solving the Two-dimensional Bin-packing Problem.” INFORMS Journal on Computing 19 (1): 36–51. doi: 10.1287/ijoc.1060.0181.
   Web of Science ®Google Scholar
• Rahmaniani, R., T. G. Crainic, M. Gendreau, and W. Rei. 2017. “The Benders Decomposition Algorithm: A Literature Review.” European Journal of Operational Research 259 (3): 801–817. doi:10.1016/j.ejor.2016.12.005.
   Web of Science ®Google Scholar
• Scheithauer, G. 2018. Introduction to Cutting and Packing Optimization: Problems, Modeling Approaches, Solution Methods. International Series in Operations Research and Management Science. Springer. doi:10.1007/978-3-319-64143-0.
   Google Scholar
• Scheithauer, G., and J. Terno. 1988. “Guillotine Cutting of Defective Boards.” Optimization 19 (1): 111–121. doi:10.1080/02331938808843323.
   Google Scholar
• Vianna, A. C. G., and M. N. Arenales. 2006. “O Problema de Corte de Placas Defeituosas.” Pesquisa Operacional 26: 185–202. doi: 10.1590/S0101-74382006000200001
   Google Scholar
• Wang, P. Y. 1983. “Two Algorithms for Constrained Two-Dimensional Cutting Stock Problems.” Operations Research 31 (3): 573–586. doi:10.1287/opre.31.3.573.
   Web of Science ®Google Scholar
• Wäscher, G., H. Haußner, and H. Schumann. 2007. “An Improved Typology of Cutting and Packing Problems.” European Journal of Operational Research 183 (3): 1109–1130. doi:10.1016/j.ejor.2005.12.047.
   Web of Science ®Google Scholar
• Yanasse, H. H., and R. Morabito. 2006. “Linear Models for 1-group Two-dimensional Guillotine Cutting Problems.” International Journal of Production Research 44 (17): 3471–3491. doi:10.1080/00207540500478603.
   Web of Science ®Google Scholar
• Yanasse, H. H., and R. Morabito. 2008. “A Note on Linear Models for Two-group and Three-group Two-dimensional Guillotine Cutting Problems.” International Journal of Production Research 46 (21): 6189–6206. doi:10.1080/00207540601011543.
   Web of Science ®Google Scholar