Help
Cart
Skip main navigation

Available Issues

April 12, 2013 - October 16, 2026

Available Issues

April 12, 2013 - October 16, 2026

Exact Algorithms for Two-Dimensional Knapsack Problems: A Unified Framework with New Benchmark Results

Published Online:23 Oct 2026https://doi.org/10.1287/ijoc.2025.1423

References

  • Baldacci R, Boschetti MA (2007) A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem. Eur. J. Oper. Res. 183(3):1136–1149.Crossref, Google Scholar
  • Baldacci R, Coniglio S, Cordeau JF, Furini F (2024) A numerically exact algorithm for the bin-packing problem. INFORMS J. Comput. 36(1):141–162.Link, 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
  • 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
  • Berkey JO, Wang PY (1987) Two-dimensional finite bin-packing algorithms. J. Oper. Res. Soc. 38(5):423–429.Crossref, Google Scholar
  • Birgin EG, Lobato RD, Morabito R (2012) Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm. J. Oper. Res. Soc. 63(2):183–200.Crossref, Google Scholar
  • Boschetti MA, Montaletti L (2010) An exact algorithm for the two-dimensional strip-packing problem. Oper. Res. 58(6):1774–1791.Link, Google Scholar
  • Boschetti MA, Mingozzi A, Hadjiconstantinou E (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
  • Caprara A, Monaci M (2004) On the two-dimensional knapsack problem. Oper. Res. Lett. 32(1):5–14.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, Iori M (2018) The meet-in-the-middle principle for cutting and packing problems. INFORMS J. Comput. 30(4):646–661.Link, Google Scholar
  • Côté JF, Dell’Amico M, Iori M (2014) Combinatorial Benders’ cuts for the strip packing problem. Oper. Res. 62(3):643–661.Link, Google Scholar
  • Côté JF, Haouari M, Iori M (2021) Combinatorial Benders decomposition for the two-dimensional bin packing problem. INFORMS J. Comput. 33(3):963–978.Link, Google Scholar
  • de Almeida Cunha JG, De Lima VL, De Queiroz TA (2020) Grids for cutting and packing problems: A study in the 2D knapsack problem. 4OR. 18(3):293–339.Crossref, Google Scholar
  • de Queiroz TA, Hokama PHDB, Schouery RCS, Miyazawa FK (2017) Two-dimensional disjunctively constrained knapsack problem: Heuristic and exact approaches. Comput. Indust. Engrg. 105:313–328.Crossref, Google Scholar
  • Desrosiers J, Lübbecke M, Desaulniers G, Gauthier JB (2024) Branch-and-Price (GERAD, HÉC, Montréal).Google Scholar
  • Fayard D, Hifi M, Zissimopoulos V (1998) An efficient approach for large-scale two-dimensional guillotine cutting stock problems. J. Oper. Res. Soc. 49(12):1270–1277.Crossref, Google Scholar
  • Fekete SP, Schepers J (1997) A new exact algorithm for general orthogonal d-dimensional knapsack problems. Burkard R, Woeginger G, eds. Algorithms—ESA 1997 (Springer, Berlin, Heidelberg), 144–156.Crossref, Google Scholar
  • Fekete SP, Schepers J (2001) New classes of fast lower bounds for bin packing problems. Math. Programming 91(1):11–31.Crossref, 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
  • Garey M, Johnson D (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, Mathematical Sciences Series (W. H. Freeman, San Francisco).Google Scholar
  • Hadjiconstantinou E, Christofides N (1995) An exact algorithm for general, orthogonal, two-dimensional knapsack problems. Eur. J. Oper. Res. 83(1):39–56.Crossref, Google Scholar
  • Held S, Cook W, Sewell EC (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Programming Comput. 4(4):363–381.Crossref, Google Scholar
  • Herz J (1972) Recursive computational procedure for two-dimensional stock cutting. IBM J. Res. Development 16(5):462–469.Crossref, Google Scholar
  • Hifi M (2001) Exact algorithms for large-scale unconstrained two and three staged cutting problems. Comput. Optim. Appl. 18(1):63–88.Crossref, Google Scholar
  • Hifi M, Zissimopoulos V (1996a) A recursive exact algorithm for weighted two-dimensional cutting. Eur. J. Oper. Res. 91(3):553–564.Crossref, Google Scholar
  • Hifi M, Zissimopoulos V (1996b) Une amélioration de l’algorithme récursif de herz pour le problème de découpe à deux dimensions. RAIRO-Oper. Res. 30(2):111–125.Crossref, Google Scholar
  • Hooker JN (2000) Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction, Wiley Series in Discrete Mathematics and Optimization (Wiley, New York).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
  • Hopper E, Turton B (2002) Problem generators for rectangular packing problems. Stud. Inform. Univ. 2(1):123–136.Google Scholar
  • IBM (2015) IBM ILOG CPLEX Optimization Studio (IBM Corporation, Armonk, NY).Google Scholar
  • Iori M, de Lima VL, Martello S, Monaci M (2022) 2DPackLib: A two-dimensional cutting and packing library. Optim. Lett. 16(2):471–480.Google Scholar
  • Iori M, De Lima VL, Martello S, Miyazawa FK, Monaci M (2021) Exact solution techniques for two-dimensional cutting and packing. Eur. J. Oper. Res. 289(2):399–415.Crossref, Google Scholar
  • Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-Row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.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
  • Martello S, Vigo D (1998) Exact solution of the two-dimensional finite bin packing problem. Management Sci. 44(3):388–399.Link, Google Scholar
  • Martello S, Monaci M, Vigo D (2003) An exact approach to the strip-packing problem. INFORMS J. Comput. 15(3):310–319.Link, 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
  • Morabito R, Arenales MN, Arcaro V (1992) An and–Or-graph approach for two-dimensional cutting problems. Eur. J. Oper. Res. 58(2):263–271.Crossref, Google Scholar
  • Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2020) A generic exact solver for vehicle routing and related problems. Math. Programming 183(1–2):483–523.Crossref, Google Scholar
  • Ryan DM, Foster BA (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling (North-Holland, Amsterdam, Netherlands), 269–280.Google Scholar
  • Shiangjen K, Chaijaruwanich J, Srisujjalertwaja W, Unachak P, Somhom S (2018) An iterative bidirectional heuristic placement algorithm for solving the two-dimensional knapsack packing problem. Engrg. Optim. 50(2):347–365.Crossref, Google Scholar
  • Uchoa E, Pessoa A, Moreno L (2024) Optimizing with Column Generation: Advanced Branch-Cut-and-Price Algorithms (Part I). Technical Report L-2024-3, Cadernos do LOGIS-UFF, Universidade Federal Fluminense, Engenharia de Produção.Google Scholar
  • Wang P (1983) Two algorithms for constrained two-dimensional cutting stock problems. Oper. Res. 31(3):573–586.Link, Google Scholar
  • Wang S, Baldacci R, Liu Q, Wei L (2025a) EATKG: An open-source efficient exact algorithm for the two-dimensional knapsack problem with guillotine constraints. Eur. J. Oper. Res. 327(3):735–753.Google Scholar
  • Wang S, Baldacci R, Furini F, Wei L, Liu Q (2025b) A highly efficient numerically exact algorithm for two-dimensional bin-packing problems. Preprint, submitted September 21, https://ssrn.com/abstract=5515822.Google Scholar
  • Wang S, Baldacci R, Furini F, Wei L, Liu Q (2026) Exact algorithms for two-dimensional knapsack problems: A unified framework with new benchmark results. https://doi.org/10.1287/ijoc.2025.1423.cd, https://github.com/INFORMSJoC/2025.1423.Google Scholar
  • Wang S, Yao S, Zhang H, Liu Q, Wei L (2025c) Arc-flow formulation and branch-and-price-and-cut algorithm for the bin-packing problem with fragile objects. Comput. Oper. Res. 173:106878.Crossref, Google Scholar
  • Wei L, Luo Z, Baldacci R, Lim A (2020) A new branch-and-price-and-cut algorithm for one-dimensional bin-packing problems. INFORMS J. Comput. 32(2):428–443.Link, Google Scholar
  • Wei L, Oon WC, Zhu W, Lim A (2011) A skyline heuristic for the 2D rectangular packing and strip packing problems. Eur. J. Oper. Res. 215(2):337–346.Google Scholar
  • Wei L, Qin H, Cheang B, Xu X (2016) An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem. Internat. Trans. Oper. Res. 23(1–2):65–92.Crossref, Google Scholar
  • Yao S, Zhang H, Liu Q, Leng J, Wei L (2024) Combinatorial Benders’ decomposition for the constrained two-dimensional non-guillotine cutting problem with defects. Internat. J. Production Res. 62(23):8299–8325.Crossref, Google Scholar
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree