Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming

References

• Alvarez-Valdes R, Parajon A, Tamarit JM (2002) A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems. Comput. Oper. Res. 29(7):925–947.Crossref, Google Scholar
• Arbib C, Marinelli F, Rossi F, di Iorio F (2002) Cutting and reuse: An application from automobile component manufacturing. Oper. Res. 50(6):923–934.Link, Google Scholar
• Beasley JE (2016) OR-Library. Accessed February 1, 2016, http://people.brunel.ac.uk/∼mastjjb/jeb/info.html.Google Scholar
• Ben Messaoud S, Chu C, Espinouse M (2008) Characterization and modelling of guillotine constraints. Eur. J. Oper. Res. 191(1):112–126.Crossref, Google Scholar
• Bennell JA, Oliveira JF, Wäscher G (2013) Cutting and packing. Internat. J. Production Econom. 145(2):449–450.Crossref, Google Scholar
• Boschetti M, Hadjiconstantinou E, Mingozzi A (2002) New upper bounds for the two-dimensional orthogonal non guillotine cutting stock problem. IMA J. Management Math. 13(2):95–119.Crossref, Google Scholar
• Burke E, Hellier R, Kendall G, Whitwell G (2006) A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem. Oper. Res. 54(3):587–601.Link, Google Scholar
• Caprara A, Monaci M (2004) On the two-dimensional knapsack problem. Oper. Res. Lett. 32(1):5–14.Crossref, Google Scholar
• Chen Y (2008) A recursive algorithm for constrained two-dimensional cutting problems. Comput. Optim. Appl. 41(3):337–347.Crossref, Google Scholar
• Christofides N, Hadjiconstantinou E (1995) An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts. Eur. J. Oper. Res. 83(1):21–38.Crossref, Google Scholar
• Christofides N, Whitlock C (1977) An algorithm for two-dimensional cutting problems. Oper. Res. 25(1):30–44.Link, Google Scholar
• Cintra G, Wakabayashi Y (2004) Dynamic programming and column generation based approaches for two-dimensional guillotine cutting problems. Experimental and Efficient Algorithms, Lecture Notes in Computer Science, Vol. 3059 (Springer, Berlin), 175–190.Crossref, Google Scholar
• Clautiaux F, Jouglet A, Moukrim A (2013) A new graph-theoretical model for the guillotine-cutting problem. INFORMS J. Comput. 25(1):72–86.Link, Google Scholar
• Coffman EG, Garey MR, Johnson DS, Tarjan RE (1980) Performance bounds for level- oriented two-dimensional packing algorithms. SIAM J. Comput. 9(4):808–826.Crossref, Google Scholar
• Cung V-D, Hifi M, Le Cun B (2000) Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm. Internat. Trans. Oper. Res. 7(3):185–210.Crossref, Google Scholar
• Dolatabadi M, Lodi A, Monaci M (2012) Exact algorithms for the two-dimensional guillotine knapsack. Comput. Oper. Res. 39(1):48–53.Crossref, Google Scholar
• Dyckhoff H (1981) A new linear programming approach to the cutting stock problem. Oper. Res. 29(6):1092–1104.Link, Google Scholar
• Fekete SP, Schepers J, van der Veen JC (2007) An exact algorithm for higher-dimensional orthogonal packing. Oper. Res. 55(3):569–587.Link, Google Scholar
• Fleszar K (2016) An exact algorithm for the two-dimensional stage-unrestricted guillotine cutting/packing decision problem. INFORMS J. Comput. 28(4):703–720.Link, Google Scholar
• Furini F, Malaguti E (2013) Models for the two-dimensional two-stage cutting stock problem with multiple stock size. Comput. Oper. Res. 40(8):1953–1962.Crossref, Google Scholar
• Furini F, Malaguti E (2016) A pseudo-polynomial size formulation for 2-stage 2-dimensional knapsack problems. Proc. 45th Internat. Conf. Comput. Indust. Engrg. (Curran Associates, Red Hook, NY), 833–840.Google Scholar
• Gilmore PC, Gomory RE (1965) Multistage cutting stock problems of two and more dimensions. Oper. Res. 13(1):94–120.Link, Google Scholar
• Herz JC (1972) Recursive computational procedure for two-dimensional stock-cutting. IBM J. Res. Development 16(5):462–469.Crossref, Google Scholar
• Hifi M (1997) An improvement of Viswanathan and Bagchi’s exact algorithm for constrained two-dimensional cutting stock. Comput. Oper. Res. 24(8):727–736.Crossref, Google Scholar
• Hifi M (2004) Dynamic programming and hill-climbing techniques for constrained two-dimensional cutting stock problems. J. Combin. Optim. 8(1):65–84.Crossref, Google Scholar
• Hifi M, Roucairol C (2001) Approximate and exact algorithm for constrained (un)weighted two-dimensional two-staged cutting stock problems. J. Combin. Optim. 5(4):465–494.Crossref, Google Scholar
• Iori M, Salazar-González J-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
• Lodi A, Monaci M (2003) Integer linear programming models for 2-staged two-dimensional knapsack problems. Math. Program. 94(2):257–278.Crossref, Google Scholar
• Lodi A, Martello S, Monaci M (2002) Two-dimensional packing problems: A survey. Eur. J. Oper. Res. 141(2):241–252.Crossref, Google Scholar
• Lodi A, Martello S, Monaci M, Cicconetti C, Lenzini L, Mingozzi E, Eklund C, Moilanen J (2011) Efficient two-dimensional packing algorithms for mobile WiMAX. Management Sci. 57(12):2130–2144.Link, Google Scholar
• Macedo R, Alves C, Valério de Carvalho JM (2010) Arc-flow model for the two-dimensional guillotine cutting stock problem. Comput. Oper. Res. 37(6):991–1001.Crossref, Google Scholar
• Malaguti E, Medina Durán R, Toth P (2014) Approaches to real world two-dimensional cutting problems. Omega 47:99–115.Crossref, Google Scholar
• Pisinger D, Sigurd M (2007) Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. INFORMS J. Comput. 19(1):36–51.Link, Google Scholar
• Puchinger J, Raidl GR (2007) Models and algorithms for three-stage two-dimensional bin packing. Eur. J. Oper. Res. 183(3):1304–1327.Crossref, Google Scholar
• Russo M, Sforza A, Sterle C (2014) An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems. Comput. Oper. Res. 50:97–114.Crossref, Google Scholar
• Silva E, Alvelos F, Valério de Carvalho JM (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
• Trick M (2003) A dynamic programming approach for consistency and propagation for knapsack constraints. Ann. Oper. Res. 118(1):73–84.Crossref, Google Scholar
• Valério de Carvalho JM (2002) LP models for bin packing and cutting stock problems. Eur. J. Oper. Res. 141(2):253–273.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
• Wang PY (1983) Two algorithms for constrained two-dimensional cutting stock problems. Oper. Res. 31(3):573–586.Link, Google Scholar
• Wäscher G, Haussner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183(3):1109–1130.Crossref, Google Scholar