The Meet-in-the-Middle Principle for Cutting and Packing Problems

References

• Alvarez-Valdes R, Parreño F, Tamarit J (2005) A branch-and-cut algorithm for the pallet loading problem. Comput. Oper. Res. 32(11):3007–3029.Crossref, Google Scholar
• Alves C, Macedo R, Mrad M, Valério de Carvalho J, Alvelos F, Chan T, Silva E (2009) An exact branch-and-price algorithm for the two-dimensional cutting stock problem. Working paper, Universidade do Minho, Braga, Portugal.Google Scholar
• Beasley JE (1985a) Algorithms for unconstrained two-dimensional guillotine cutting. J. Oper. Res. Soc. 36(4):297–306.Crossref, Google Scholar
• Beasley JE (1985b) An exact two-dimensional non-guillotine cutting tree search procedure. Oper. Res. 33(1):49–64.Link, Google Scholar
• Beasley JE (1990) OR-Library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11):1069–1072.Crossref, Google Scholar
• Belov G, Rohling H (2013) LP bounds in an interval-graph algorithm for orthogonal-packing feasibility. Oper. Res. 61(2):483–497.Link, Google Scholar
• Bortfeldt A, Wäscher G (2013) Constraints in container loading. A state of the art review. Eur. J. Oper. Res. 229(1):1–20.Crossref, Google Scholar
• Boschetti M, Montaletti L (2010) An exact algorithm for the two-dimensional strip-packing problem. Oper. Res. 58(6):1774–1791.Link, Google Scholar
• Boschetti M, Hadjiconstantinou E, Mingozzi A (2002) New upper bounds for the two-dimensional othogonal non guillotine cutting stock problem. IMA J. Management Math. 13(2):95–119.Crossref, Google Scholar
• Christofides N, Whitlock C (1977) An algorithm for two-dimensional cutting problems. Oper. Res. 25(1):30–44.Link, Google Scholar
• Clautiaux F, Jouglet A, Carlier J, Moukrim A (2008) A new constraint programming approach for the orthogonal packing problem. Comput. Oper. Res. 35(3):944–959.Crossref, Google Scholar
• Côté JF, Dell’Amico M, Iori M (2014a) Combinatorial Benders’ cuts for the strip packing problem. Oper. Res. 62(3):643–661.Link, Google Scholar
• Côté JF, Gendreau M, Potvin JY (2014b) An exact algorithm for the two-dimensional orthogonal packing problem with unloading constraints. Oper. Res. 62(5):1126–1141.Link, Google Scholar
• Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: Mathematical models and exact algorithms. Eur. J. Oper. Res. 255(1):1–20.Crossref, Google Scholar
• Delorme M, Iori M, Martello S (2018) BPPLIB: A library for bin packing and cutting stock problems. Optim. Lett. 12(2):235–250.Crossref, Google Scholar
• Gilmore P, Gomory R (1965) Multistage cutting stock problems of two and more dimensions. Oper. Res. 13(1):94–120.Link, Google Scholar
• Herz J (1972) Recursive computational procedure for two-dimensional stock cutting. IBM J. Res. Development 16(5):462–469.Crossref, Google Scholar
• Hopper E, Turton B (2001) An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. Eur. J. Oper. Res. 128(1):34–57.Crossref, Google Scholar
• Horowitz W, Sahni S (1974) Computing partitions with applications to the knapsack problem. J. ACM 21(2):277–292.Crossref, Google Scholar
• Iori M, Salazar González J, Vigo D (2007) An exact approach for the vehicle routing problem with two-dimensional loading constraints. Transportation Sci. 41(2):253–264.Link, Google Scholar
• Kenmochi M, Imamichi T, Nonobe K, Yagiura M, Nagamochi H (2009) Exact algorithms for the two-dimensional strip packing problem with and without rotations. Eur. J. Oper. Res. 198(1):73–83.Crossref, Google Scholar
• Lodi A, Martello S, Vigo D (2004) Models and bounds for two-dimensional level packing problems. J. Combin. Optim. 8(1):363–379.Crossref, Google Scholar
• Macedo R, Alves C, Valério de Carvalho J (2010) Arc-flow model for the two-dimensional guillotine cutting stock problem. Comput. Oper. Res. 37(6):991–1001.Crossref, Google Scholar
• Mesyagutov M, Scheithauer G, Belov G (2012) LP bounds in various constraint programming approaches for orthogonal packing. Comput. Oper. Res. 39(10):2425–2438.Crossref, Google Scholar
• Mrad M, Meftahi I, Haouari M (2013) A branch-and-price algorithm for the two-stage guillotine cutting stock problem. J. Oper. Res. Soc. 64(5):629–637.Crossref, Google Scholar
• Scheithauer G, Terno J (1996) The G4-heuristic for the pallet loading problem. J. Oper. Res. Soc. 47(4):511–522.Crossref, Google Scholar
• Silva E, Alvelos F, Valério de Carvalho J (2010) An integer programming model for two- and three-stage two-dimensional cutting stock problems. Eur. J. Oper. Res. 205(3):699–708.Crossref, Google Scholar
• Terno J, Lindemann R, Scheithauer G (1987) Zuschnittprobleme and ihre praktische lösung. Technical report, Verlag Harry Deutsch, Thun und Frankfurt, Germany.Google Scholar
• Valério de Carvalho J (1999) Exact solution of bin-packing problems using column generation and branch-and-bound. Ann. Oper. Res. 86(January):629–659.Crossref, Google Scholar
• Vanderbeck F (2001) A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem. Management Sci. 47(6):864–879.Link, Google Scholar
• Wäscher G, Haußner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183(3):1109–1130.Crossref, Google Scholar