Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem

References

• Apt K. R.Principles of Constraint Programming (2003) (Cambridge University Press, Cambridge, UK) Crossref, Google Scholar
• Belov G. Problems, models and algorithms in one- and two-dimensional cutting. (2003) . Ph.D. thesis, Institute of Numerical Mathematics, Technischen Universität Dresden, Dresden, GermanyGoogle Scholar
• Bengtsson B. E. Packing rectangular pieces—A heuristic approach. Comput. J. (1982) 25:353–357Crossref, Google Scholar
• Berkey J. O., Wang P. Y. Two dimensional finite bin packing algorithms. J. Oper. Res. Soc. (1987) 38:423–429Crossref, Google Scholar
• Bockmayr A., Kasper T. Branch-and-infer: A unifying framework for integer and finite domain constraint programming. INFORMS J. Comput. (1998) 10:287–300Link, Google Scholar
• Boschetti M. A., Mingozzi A. The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case. 4OR (2003a) 1:27–42Crossref, Google Scholar
• Boschetti M. A., Mingozzi A. The two-dimensional finite bin packing problem. Part II: New lower and upper bounds. 4OR (2003b) 2:135–148Google Scholar
• Caprara A., Monaci M. On the two-dimensional knapsack problem. Oper. Res. Lett. (2004) 32:5–14Crossref, Google Scholar
• Chen C. S., Lee S. M., Shen Q. S. An analytical model for the container loading problem. Eur. J. Oper. Res. (1995) 80:68–76Crossref, Google Scholar
• Dell’Amico M., Martello S., Vigo D. A lower bound for the non-oriented two-dimensional bin packing problem. Discrete Appl. Math. (2002) 118:13–24Crossref, Google Scholar
• Dowsland K. Some experiments with simulated annealing techniques for packing problems. Eur. J. Oper. Res. (1993) 68:389–399Crossref, Google Scholar
• Eremin A., Wallace M., Walsh T. Hybrid Benders decomposition algorithms in constraint logic programming. CP 2001, Lecture Notes in Computer Science (2001) 2239(Springer, Berlin, Germany) 1–15Crossref, Google Scholar
• Faroe O., Pisinger D., Zachariasen M. Guided local search for the three-dimensional bin packing problem. INFORMS J. Comput. (2003) 15:267–283Link, Google Scholar
• Fekete Sandor P., Schepers Joerg. New classes of lower bounds for the bin packing problem. Math. Programming (2001) 91:11–31Crossref, Google Scholar
• Fekete Sandor P., Schepers Joerg, van der Veen Jan C. An exact algorithm for higher-dimensional orthogonal packing. Oper. Res. (2007) . ForthcomingLink, Google Scholar
• Gilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem. Oper. Res. (1961) 9:849–859Link, Google Scholar
• Gilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem—Part II. Oper. Res. (1963) 13:94–119Link, Google Scholar
• Gilmore P. C., Gomory R. E. Multistage cutting stock problems of two and more dimensions. Oper. Res. (1965) 13:94–120Link, 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
• Hifi M. Exact algorithms for large-scale unconstrained two and three staged unconstrained cutting problems. Comput. Optim. Appl. (2001) 18:63–88Crossref, Google Scholar
• ILOGILOG CPLEX 7.0, Reference Manual (2000) . ILOG SA, Gentilly, FranceGoogle Scholar
• Junger Michael, Thienel Stafan. The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization. Software Practice Experience (2000) 30(11):1325–1352Crossref, Google Scholar
• Junker U., Karisch S. E., Kohl N., Vaaben B., Fahle T., Sellmann M., Jaffar J. Constraint programming based column generation for crew assignment. Proc. CP’99, Lecture Notes in Computer Science (1999) 1713(Springer, Berlin, Germany) 261–274Google Scholar
• Kellerer H., Pferschy U., Pisinger D.Knapsack Problems (2004) (Springer, Berlin, Germany) Crossref, Google Scholar
• Lasdon L. S.Optimization Theory for Large Systems (1970) (Macmillan, London, UK) Google Scholar
• Lodi A., Martello S., Vigo D. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS J. Comput. (1999) 11:345–357Link, Google Scholar
• Lodi A., Martello S., Vigo D. Recent advances on two-dimensional bin packing problems. Discrete Appl. Math. (2002) 123:379–396Crossref, 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., den Boef Edgar, Korst Jan. Algorithms for general and robot-packable variants of the three-dimensional bin packing problem. ACM Trans. Math. Software (2007) 33(1Crossref, Google Scholar
• Monaci M., Toth P. A set-covering based heuristic approach for bin-packing problems. INFORMS J. Comput. (2006) 18(1):71–85Link, Google Scholar
• Onodera H., Taniguchi Y., Tamaru K. Branch-and-bound placement for building block layout. Proc. 28th ACM/IEEE Design Automation Conf. (1991) (ACM Press, New York) 433–439Crossref, Google Scholar
• Padberg M. Packing small boxes into a big box. Math. Methods Oper. Res. (2000) 52:1–21Crossref, Google Scholar
• Parada V., Palma R., Sales D., Gómes A. A comparative numerical analysis for the guillotine two-dimensional cutting problem. Ann. Oper. Res. (2000) 96:245–254Crossref, Google Scholar
• Pisinger D., Sigurd M. M. The two-dimensional bin packing problem with variable bin sizes and costs. Discrete Optim. (2005) 2:154–167Crossref, Google Scholar
• Ryan D. M., Foster B. A., Wren A. An integer programming approach to scheduling. Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling (1981) (North-Holland, Amsterdam, The Netherlands) 269–280Google Scholar
• Voudouris C. Guided local search for combinatorial optimisation problems. (1997) . Ph.D. thesis, Department of Computer Science, University of Essex, Colchester, UKGoogle Scholar
• Voudouris C., Tsang E. Guided local search and its application to the traveling salesman problem. Eur. J. Oper. Res. (1999) 113:469–499Crossref, Google Scholar