LP Bounds in an Interval-Graph Algorithm for Orthogonal-Packing Feasibility

References

• Alvarez-Valdes R, Parreño F, Tamarit JM. A branch and bound algorithm for the strip packing problem. OR Spectrum (2009) 31(2):431–459Crossref, Google Scholar
• Amaral A, Letchford AN. An improved upper bound for the two-dimensional non-guillotine cutting problem. (2003) . Technical report, Lancaster University, Lancaster, UKGoogle Scholar
• Baldacci R, Boschetti MA. A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem. Eur. J. Oper. Res. (2007) 183(3):1136–1149Crossref, Google Scholar
• Beasley JE. Bounds for two-dimensional cutting. J. Oper. Res. Soc. (1985) 36(1):71–74Crossref, Google Scholar
• Beldiceanu N, Carlsson M, Demassey S, Poder E. New filtering for the cumulative constraint in the context of non-overlapping rectangles. Ann. Oper. Res. (2011) 184:27–50Crossref, Google Scholar
• Belov G, Kartak V, Rohling H, Scheithauer G. One-dimensional relaxations and LP bounds for orthogonal packing. Internat. Trans. Oper. Res. (2009) 16(6):745–766Crossref, Google Scholar
• Belov G, Kartak V, Rohling H, Scheithauer G. Conservative scales in packing problems. OR Spectrum (2013) 35(2):505–542Crossref, Google Scholar
• Boschetti MA, Montaletti L. An exact algorithm for the two-dimensional strip-packing problem. Oper. Res. (2010) 58(6):1774–1791Link, Google Scholar
• Boschetti MA, Mingozzi A, Hadjiconstantinou E. New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem. IMA J. Management Math. (2002) 13(2):95–119Crossref, Google Scholar
• Caprara A, Monaci M. Bidimensional packing by bilinear programming. Math. Programming (2009) 118(1):75–108Crossref, Google Scholar
• Clautiaux F, Jouglet A, Moukrim A, McGeoch CC. A new graph-theoretical model for k-dimensional guillotine-cutting problems. Experimental Algorithms (2008b) 5038(Springer, Berlin) 43–54Lecture Notes in Computer ScienceCrossref, Google Scholar
• Clautiaux F, Jouglet A, Carlier J, Moukrim A. A new constraint programming approach for the orthogonal packing problem. Comput. Oper. Res. (2008a) 35(3):944–959Crossref, Google Scholar
• Fekete SP, Schepers J. A combinatorial characterization of higher-dimensional orthogonal packing. Math. Oper. Res. (2004a) 29(2):353–368Link, Google Scholar
• Fekete SP, Schepers J. A general framework for bounds for higher-dimensional orthogonal packing problems. Math. Methods Oper. Res. (2004b) 60(2):311–329Crossref, Google Scholar
• Fekete SP, Schepers J, van der Veen J. An exact algorithm for higher-dimensional orthogonal packing. Oper. Res. (2007) 55(3):569–587Link, Google Scholar
• Ferreira EP, Oliveira JF, Bortfeldt A, Homberger J, Kopfer H, Pankratz G, Strangmeier R. Fekete and Schepers' graph-based algorithm for the two-dimensional orthogonal packing problem revisited. Intelligent Decision Support (2008) (Gabler, Wiesbaden, Germany) 15–31Crossref, Google Scholar
• Gilmore PC, Gomory RE. A linear programming approach to the cutting-stock problem (Part I). Oper. Res. (1961) 9:849–859Link, Google Scholar
• Golumbic MC. Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics (2004) 572nd ed.(Elsevier B.V., Amsterdam) Google Scholar
• Hopper E. Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods. (2000) . Ph.D. thesis, Cardiff University, Cardiff, UKGoogle Scholar
• Hopper E, Turton BCH. An empirical investigation of metaheuristic and heuristic algorithms for a 2D-packing problem. Eur. J. Oper. Res. (2000) 128(1):34–57Crossref, Google Scholar
• Kenmochi M, Imamichi T, Nonobe K, Yagiura M, Nagamochi H. Exact algorithms for the two-dimensional strip packing problem with and without rotations. Eur. J. Oper. Res. (2009) 198(1):73–83Crossref, Google Scholar
• Korf RE, Zilberstein S, Koehler J, Koenig S. Optimal rectangle packing: New results. Proc. Fourteenth Internat. Conf. Automated Planning and Scheduling (ICAPS 2004) (2004) (Whistler, British Columbia, Canada) 142–149Google Scholar
• Macedo R, Alves C, Valério de Carvalho JM. Arc-flow model for the two-dimensional guillotine cutting stock problem. Comput. Oper. Res. (2010) 37(6):991–1001Crossref, Google Scholar
• Martello S, Monaci M, Vigo D. An exact approach to the strip-packing problem. INFORMS J. Comput. (2003) 15(3):310–319Link, Google Scholar
• Martin A, Jünger M, Naddef D. General mixed-integer programming: Computational issues for branch-and-cut algorithms. Computational Combinatorial Optimization (2001) 2241(Springer, Berlin) 1–25Lecture Notes in Computer ScienceCrossref, Google Scholar
• Mesyagutov M, Scheithauer G, Belov G. LP bounds in various constraint programming approaches for orthogonal packing. Comput. Oper. Res. (2012) 39(10):2425–2438Crossref, Google Scholar
• Padberg M. Packing small boxes into a big box. Math. Methods Oper. Res. (2000) 52(1):1–21Crossref, Google Scholar
• Pisinger D, Sigurd MM. Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. INFORMS J. Comput. (2007) 19(1):36–51Link, Google Scholar
• Rietz J, Scheithauer G, Terno J. Families of non-IRUP instances of the one-dimensional cutting stock problem. Discrete Appl. Math. (2002) 121:229–245Crossref, Google Scholar
• Rohling H. LP bounds in exact algorithms for two-dimensional orthogonal packing. (2008) . Diploma thesis, Dresden University of Technology, Dresden, GermanyGoogle Scholar
• Scheithauer G. LP-based bounds for the container and multi-container loading problem. Internat. Trans. Oper. Res. (1999) 6(2):199–213Crossref, Google Scholar
• Simonis H, O'Sullivan B, Stuckey PJ. Search strategies for rectangle packing. Principles and Practice of Constraint Programming (2008) 5202(Springer, Berlin) 52–66Lecture Notes in Computer ScienceCrossref, Google Scholar