Combinatorial Benders' decomposition for the constrained two-dimensional non-guillotine cutting problem with defects

References

• Afsharian, Mohsen, Ali Niknejad, and Gerhard Wäscher. 2014. “A Heuristic, Dynamic Programming-based Approach for a Two-dimensional Cutting Problem with Defects.” OR Spectrum 36 (4): 971–999. https://doi.org/10.1007/s00291-014-0363-x.
   Web of Science ®Google Scholar
• Aksu, Dilek Tuzun, and Bahadır Durak. 2016. “A Dynamic Programming Algorithm for the Online Cutting Problem with Defects and Quality Grades.” IFAC-PapersOnLine 49 (12): 17–22. https://doi.org/10.1016/j.ifacol.2016.07.543.
   Google Scholar
• Alvarez-Valdes, Ramón, Francisco Parreño, and José Manuel Tamarit. 2005. “A GRASP Algorithm for Constrained Two-dimensional Non-guillotine Cutting Problems.” Journal of the Operational Research Society 56 (4): 414–425. https://doi.org/10.1057/palgrave.jors.2601829.
   Web of Science ®Google Scholar
• Alvarez-Valdes, R., F. Parreño, and J. M. Tamarit. 2007. “A Tabu Search Algorithm for a Two-dimensional Non-guillotine Cutting Problem.” European Journal of Operational Research 183 (3): 1167–1182. https://doi.org/10.1016/j.ejor.2005.11.068.
   Web of Science ®Google Scholar
• Alvarez-Valdes, Ramón, Francisco Parreño, and José Manuel Tamarit. 2009. “A Branch and Bound Algorithm for the Strip Packing Problem.” OR Spectrum 31 (2): 431–459. https://doi.org/10.1007/s00291-008-0128-5.
   Web of Science ®Google Scholar
• Baldacci, Roberto, and Marco A. Boschetti. 2007. “A Cutting-plane Approach for the Two-dimensional Orthogonal Non-guillotine Cutting Problem.” European Journal of Operational Research 183 (3): 1136–1149. https://doi.org/10.1016/j.ejor.2005.11.060.
   Web of Science ®Google Scholar
• Beasley, J. E. 1985. “An Exact Two-dimensional Non-guillotine Cutting Tree Search Procedure.” Operations Research 33 (1): 49–64. https://doi.org/10.1287/opre.33.1.49.
   Web of Science ®Google Scholar
• Beasley, J. E. 2004. “A Population Heuristic for Constrained Two-dimensional Non-guillotine Cutting.” European Journal of Operational Research 156 (3): 601–627. https://doi.org/10.1016/S0377-2217(03)00139-5.
   Web of Science ®Google Scholar
• Boschetti, Marco A., Aristide Mingozzi, and Eleni Hadjiconstantinou. 2002. “New Upper Bounds for the Two-dimensional Orthogonal Non-guillotine Cutting Stock Problem.” IMA Journal of Management Mathematics 13 (2): 95–119. https://doi.org/10.1093/imaman/13.2.95.
   Google Scholar
• Carnieri, Celso, Guillermo A. Mendoza, and William G. Luppold. 1993. “Optimal Cutting of Dimension Parts From Lumber with a Defect: a Heuristic Solution Procedure.” Forest Products Journal 43 (9): 66–72.
   Web of Science ®Google Scholar
• Côté, Jean-François, Mauro Dell'Amico, and Manuel Iori. 2014. “Combinatorial Benders' Cuts for the Strip Packing Problem.” Operations Research 62 (3): 643–661. https://doi.org/10.1287/opre.2013.1248.
   Web of Science ®Google Scholar
• Côté, Jean-François, Michel Gendreau, and Jean-Yves Potvin. 2014. “An Exact Algorithm for the Two-dimensional Orthogonal Packing Problem with Unloading Constraints.” Operations Research 62 (5): 1126–1141. https://doi.org/10.1287/opre.2014.1307.
   Web of Science ®Google Scholar
• Côté, Jean-François, Mohamed Haouari, and Manuel Iori. 2021. “Combinatorial Benders Decomposition for the Two-dimensional Bin Packing Problem.” INFORMS Journal on Computing 33 (3): 963–978. https://doi.org/10.1287/ijoc.2020.1014.
   Web of Science ®Google Scholar
• Côté, Jean-François, and Manuel Iori. 2018. “The Meet-in-the-middle Principle for Cutting and Packing Problems.” INFORMS Journal on Computing 30 (4): 646–661. https://doi.org/10.1287/ijoc.2018.0806.
   Web of Science ®Google Scholar
• Dell'Amico, Mauro, Maxence Delorme, Manuel Iori, and Silvano Martello. 2019. “Mathematical Models and Decomposition Methods for the Multiple Knapsack Problem.” European Journal of Operational Research 274 (3): 886–899. https://doi.org/10.1016/j.ejor.2018.10.043.
   Web of Science ®Google Scholar
• Delorme, Maxence, Manuel Iori, and Silvano Martello. 2017. “Logic Based Benders' Decomposition for Orthogonal Stock Cutting Problems.” Computers & Operations Research 78: 290–298. https://doi.org/10.1016/j.cor.2016.09.009.
   Web of Science ®Google Scholar
• Durak, Bahadır, and Dilek Tuzun 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 75 (24): 7398–7411. https://doi.org/10.1080/00207543.2017.1349951.
   Google Scholar
• Gilmore, Paul C., and Ralph E. Gomory. 1961. “A Linear Programming Approach to the Cutting-stock Problem.” Operations Research 9 (6): 849–859. https://doi.org/10.1287/opre.9.6.849.
   Web of Science ®Google Scholar
• Gilmore, Paul C., and Ralph E. Gomory. 1965. “Multistage Cutting Stock Problems of Two and More Dimensions.” Operations Research 13 (1): 94–120. https://doi.org/10.1287/opre.13.1.94.
   Web of Science ®Google Scholar
• Gonçalves, José Fernando, and Gerhard Wäscher. 2020. “A MIP Model and a Biased Random-key Genetic Algorithm Based Approach for a Two-dimensional Cutting Problem with Defects.” European Journal of Operational Research 286 (3): 867–882. https://doi.org/10.1016/j.ejor.2020.04.028.
   Web of Science ®Google Scholar
• Hadjiconstantinou, Eleni, and Nicos Christofides. 1995. “An Exact Algorithm for General, Orthogonal, Two-dimensional Knapsack Problems.” European Journal of Operational Research 83 (1): 39–56. https://doi.org/10.1016/0377-2217(93)E0278-6.
   Web of Science ®Google Scholar
• Herz, J. C. 1972. “Recursive Computational Procedure for Two-dimensional Stock Sutting.” IBM Journal of Research and Development 16 (5): 462–469. https://doi.org/10.1147/rd.165.0462.
   Web of Science ®Google Scholar
• Iori, Manuel, Vinícius L. De Lima, Silvano Martello, Flávio Keidi Miyazawa, and Michele Monaci. 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.
   Web of Science ®Google Scholar
• Lai, K. K., and Jimmy W. M. Chan. 1997. “Developing a Simulated Annealing Algorithm for the Cutting Stock Problem.” Computers & Industrial Engineering 32 (1): 115–127. https://doi.org/10.1016/S0360-8352(96)00205-7.
   Web of Science ®Google Scholar
• Libralesso, Luc, and Florian Fontan. 2021. “An Anytime Tree Search Algorithm for the 2018 ROADEF/EURO Challenge Glass Cutting Problem.” European Journal of Operational Research 291 (3): 883–893. https://doi.org/10.1016/j.ejor.2020.10.050.
   Web of Science ®Google Scholar
• Luo, Qiang, Yunqing Rao, Xiaoqiang Guo, and Bing Du. 2022. “A Biased Genetic Algorithm Hybridized with VNS for the Two-dimensional Knapsack Packing Problem with Defects.” Applied Soft Computing 118: 108479. https://doi.org/10.1016/j.asoc.2022.108479.
   Web of Science ®Google Scholar
• Martin, Mateus, Pedro H. D. B. Hokama, Reinaldo Morabito, and Pedro Munari. 2020. “The Constrained Two-dimensional Guillotine Cutting Problem with Defects: An ILP Formulation, a Benders Decomposition and a CP-based Algorithm.” International Journal of Production Research 58 (9): 2712–2729. https://doi.org/10.1080/00207543.2019.1630773.
   Web of Science ®Google Scholar
• Martin, Mateus, Reinaldo Morabito, and Pedro Munari. 2022. “Two-stage and One-group Two-dimensional Guillotine Cutting Problems with Defects: A CP-based Algorithm and ILP Formulations.” International Journal of Production Research 60 (6): 1854–1873. https://doi.org/10.1080/00207543.2021.1876270.
   Web of Science ®Google Scholar
• Neidlein, Vera, André Scholz, and Gerhard Wäscher. 2016. “SLOPPGEN: A Problem Generator for the Two-dimensional Rectangular Single Large Object Placement Problem with Defects.” International Transaction in Operational Research 23 (1-2): 173–186. https://doi.org/10.1111/itor.12119.
   Web of Science ®Google Scholar
• Neidlein, Vera, Andréa C. G. Vianna, Marcos N. Arenales, and Gerhard Wäscher. 2009. “Two-dimensional Guillotineable-layout Cutting Problems with A Single Defect-an AND/OR-Graph Approach.” In Operations Research Proceedings 2008, edited by Bernhard Fleischmann, Karl-Heinz Borgwardt, Robert Klein, and Axel Tuma, 85–90. Berlin: Springer. https://doi.org/10.1007/978-3-642-00142-0_14.
   Google Scholar
• Parreño, F., M. T. Alonso, and R Alvarez-Valdes. 2020. “Solving a Large Cutting Problem in the Glass Manufacturing Industry.” European Journal of Operational Research 287 (1): 378–388. https://doi.org/10.1016/j.ejor.2020.05.016.
   Web of Science ®Google Scholar
• Parreño, F., and R. Alvarez-Valdes. 2021. “Mathematical Models for a Cutting Problem in the Glass Manufacturing Industry.” Omega 103: 102432. https://doi.org/10.1016/j.omega.2021.102432.
   Web of Science ®Google Scholar
• Vianna, Andréa Carla Gonçalves, and Marcos Nereu Arenales. 2006. “O Problema De Corte De Placas Defeituosas.” Pesquisa Operacional 26 (2): 185–202. https://doi.org/10.1590/S0101-74382006000200001.
   Google Scholar
• 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–1130. https://doi.org/10.1016/j.ejor.2005.12.047.
   Web of Science ®Google Scholar
• Yin, Aihua, Chong Chen, Dongping Hu, Jianghai Huang, and Fan Yang. 2019. “An Improved Heuristic-dynamic Programming Algorithm for Rectangular Cutting Problem.” In International Symposium on Parallel Architectures, Algorithms and Programming, 221–233. Singapore: Springer. https://doi.org/10.1007/978-981-15-2767-8_21.
   Google Scholar
• Zhang, Hao, Shaowen Yao, Qiang Liu, Lijun Wei, Libin Lin, and Jiewu Leng. 2023. “An Exact Approach for the Constrained Two-dimensional Guillotine Cutting Problem with Defects.” International Journal of Production Research 61 (9): 2986–3003. https://doi.org/10.1080/00207543.2022.2074907.
   Web of Science ®Google Scholar