An Exact Algorithm for Higher-Dimensional Orthogonal Packing

References

• Applegate D., Bixby R., Chvátal V., Cook W. On the solution of traveling salesman problems. Documenta Mathematica J. Deutschen Mathematiker-Vereinigung (1998) ICM III:645–656Google Scholar
• Arenales M., Morabito R. An AND/OR-graph approach to the solution of two-dimensional nonguillotine cutting problems. Eur. J. Oper. Res. (1995) 84:599–617Crossref, Google Scholar
• Beasley J. E. An exact two-dimensional non-guillotine cutting stock tree search procedure. Oper. Res. (1985) 33:49–64Link, Google Scholar
• Beasley J. E. OR-Library: Distributing test problems by electronic mail. J. Oper. Res. Soc. (1990) 41:1069–1072Crossref, Google Scholar
• Biró M., Boros E. Network flows and nonguillotine cutting patterns. Eur. J. Oper. Res. (1984) 16:215–221Crossref, Google Scholar
• Caprara A., Monaci M. On the 2-dimensional knapsack problem. Oper. Res. Lett. (2004) 32:5–14Crossref, Google Scholar
• Christofides N., Whitlock C. An algorithm for two-dimensional cutting problems. Oper. Res. (1977) 25:31–44Link, Google Scholar
• Dongarra J. J. Performance of various computers using standard linear equations software. (2004) . Working paper, University of Tennessee, Knoxville, TN. Continuous updates available at http://www.netlib.org/benchmarks/performance.psGoogle Scholar
• Dowsland K. A. An exact algorithm for the pallet loading problem. Eur. J. Oper. Res. (1987) 31:78–84Crossref, Google Scholar
• Fekete S. P., Schepers J. A new exact algorithm for general orthogonal d-dimensional knapsack problems. Algorithms—ESA ’97. Springer Lecture Notes in Computer Science (1997a) 1284(Springer)144–156Crossref, Google Scholar
• Fekete S. P., Schepers J. On more-dimensional packing I: Modeling. (1997b) . ZPR Technical Report 97-288. http://www.zpr.uni-koeln.de/∼paperGoogle Scholar
• Fekete S. P., Schepers J. On more-dimensional packing II: Bounds. (1997c) . ZPR Technical Report 97-289. http://www.zpr.uni-koeln.de/∼paperGoogle Scholar
• Fekete S. P., Schepers J. On more-dimensional packing III: Exact algorithms. (1997d) . ZPR Technical Report 97–290. http://www.zpr.uni-koeln.de/∼paperGoogle Scholar
• Fekete S. P., Schepers J. New classes of lower bounds for bin packing problems. Math. Programming (2001) 91:11–31Crossref, Google Scholar
• Fekete S. P., Schepers J. A combinatorial characterization of higher-dimensional orthogonal packing. Math. Oper. Res. (2004a) 29:353–368[Journal version of S. P. Fekete, J. Schepers (1997b), http://www.zpr.uni-koeln.de/∼paperLink, Google Scholar
• Fekete S. P., Schepers J. A general framework for bounds for higher-dimensional orthogonal packing problems. Math. Methods Oper. Res. (2004b) 60:81–94[Journal version of S. P. Fekete, J. Schepers (1997c), http://www.zpr.uni-koeln.de/∼paperCrossref, Google Scholar
• Fekete S. P., van der Veen J. Packlib2: An integrated benchmark library of multi-dimensional packing probelms. Eur. J. Oper. Res. (2007) . Forthcoming. Benchmark library available at http://www.math.tu-bs.de/packlib2Crossref, Google Scholar
• Fekete S. P., Köhler E., Teich J. Higher-dimensional packing with order constraints. Algorithms and Data Structures (WADS 2001). Springer Lecture Notes in Computer Science (2001) 2125:192–204Full version to appear in SIAM J. Discrete Math.Crossref, Google Scholar
• Ferreira E. P., Oliveira J. F. A note on Fekete and Schepers’ algorithm for the non-guillotinable two-dimensional packing problem. (2005) . Technical report. http://paginas.fe.up.pt/∼jfo/techreports/Fekete%20and%20Schepers%20OPP%20degeneracy.pdfGoogle Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (Freeman, San Francisco, CA) Google Scholar
• Ghouilà-Houri A. Caractérization des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d’une relation d’ordre. C.R. Acad. Sci. Paris (1962) 254:1370–1371Google Scholar
• Gilmore P. C., Hoffmann A. J. A characterization of comparability graphs and of interval graphs. Canadian J. Math. (1964) 16:539–548Crossref, Google Scholar
• Golumbic M. C.Algorithmic Graph Theory and Perfect Graphs (1980) (Academic Press, New York) Crossref, Google Scholar
• Grötschel M. On the symmetric travelling salesman problem: Solution of a 120-city problem. Math. Programming Stud. (1980) 12:61–77Crossref, Google Scholar
• Hadjiconstantinou E., Christofides N. An exact algorithm for general, orthogonal, two-dimensional knapsack problems. Eur. J. Oper. Res. (1995) 83:39–56Crossref, Google Scholar
• Hochbaum D.Approximation Algorithms for NP-Hard Problems (1996) (PWS Publishing, Boston, MA) Google Scholar
• Korte N., Möhring R. H. An incremental linear-time algorithm for recognizing interval graphs. SIAM J. Comput. (1989) 18:68–81Crossref, Google Scholar
• Martello S., Toth P.Knapsack Problems—Algorithms and Computer Implementations (1990) (Wiley, Chichester, UK) Google Scholar
• Martello S., Vigo D. Exact solution of the two-dimensional finite bin packing problem. Management Sci. (1998) 44:388–399Link, Google Scholar
• Martello S., Pisinger D., Vigo D. The three-dimensional bin packing problem. Oper. Res. (2000) 48:256–267Link, Google Scholar
• Mehlhorn K.Data Structures and Efficient Algorithms, Vol. 1: Sorting and Searching (1984) (Springer Verlag, Berlin, Germany) Google Scholar
• Nemhauser G., Wolsey L.Integer and Combinatorial Optimization (1988) (Wiley, Chichester, UK) Crossref, Google Scholar
• Padberg M. Packing small boxes into a big box. Math. Methods Oper. Res. (2000) 52:1–21Crossref, Google Scholar
• Papadimitriou C. H.Computational Complexity (1994) (Addison Wesley, New York) Google Scholar
• Schepers J.Exakte Algorithmen für orthogonale Packungsprobleme (1997) . Dissertation, Universität zu Köln, Köln, Germany. http://www.zpr.uni-koeln.de/∼paperGoogle Scholar
• Teich J., Fekete S. P., Schepers J. Optimal hardware reconfigurations techniques. J. Supercomputing (2001) 19:57–75Crossref, Google Scholar
• Wang P. Y. Two algorithms for constrained two-dimensional cutting stock problems. Oper. Res. (1983) 31:573–586Link, Google Scholar
• Wottawa M.Struktur und algorithmische Behandlung von praxisorientierten dreidimensionalen Packungsproblemen (1996) . Dissertation, Mathematisches Institut, Universität zu Köln, Köln, Germany. http://www.zpr.uni-koeln.de/∼paperGoogle Scholar