An Efficient Solver for Integral Flows in Decision Hypergraphs with Applications to Orthogonal Knapsack Problems

References

• Alvarez-Valdés R, Parajón 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
• Beasley J (1985) Algorithms for unconstrained two-dimensional guillotine cutting. J. Oper. Res. Soc. 36(4):297–306.Crossref, Google Scholar
• Beasley J (2004) A population heuristic for constrained two-dimensional non-guillotine cutting. Eur. J. Oper. Res. 156(3):601–627.Crossref, Google Scholar
• Becker H, Araújo O, Buriol LS (2022) Enhanced formulation for the guillotine 2d cutting knapsack problem. Math. Programming Comput. 14(4):673–697.Crossref, Google Scholar
• Becker H, Martin M, Araujo O, Buriol LS, Morabito R (2024) Comparative analysis of mathematical formulations for the two-dimensional guillotine cutting problem. Internat. Trans. Oper. Res. 31(5):3010–3035.Crossref, Google Scholar
• Boland N, Hewitt M, Marshall L, Savelsbergh M (2017) The continuous-time service network design problem. Oper. Res. 65(5):1303–1321.Link, 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
• Clautiaux F, Sadykov R, Vanderbeck F, Viaud Q (2018) Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem. Discrete Optim. 29:18–44.Crossref, Google Scholar
• Clautiaux F, Hanafi S, Macedo R, Voge MÉ, Alves C (2017) Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints. Eur. J. Oper. Res. 258(2):467–477.Crossref, Google Scholar
• Côté MC, Gendron B, Rousseau LM (2010) Grammar-based integer programming models for multi-activity shift scheduling. Electron. Notes Discrete Math. 36:727–734.Crossref, Google Scholar
• Cui Y, Huang B (2012) Heuristic for constrained t-shape cutting patterns of rectangular pieces. Comput. Oper. Res. 39(12):3031–3039.Crossref, Google Scholar
• Cung VD, 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
• 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 ’97 (Springer, Berlin), 144–156.Crossref, Google Scholar
• Furini F, Malaguti E, Thomopulos D (2016) Modeling two-dimensional guillotine cutting problems via integer programming. INFORMS J. Comput. 28(4):736–751.Link, Google Scholar
• Gurobi Optimization, LLC (2024) Gurobi Optimizer reference manual. Accessed July 7, 2026, https://www.gurobi.com.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
• 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
• Lodi A, Monaci M (2003) Integer linear programming models for 2-staged two-dimensional knapsack problems. Math. Programming 94(2):257–278.Crossref, Google Scholar
• Léonard A, Clautiaux F (2026) An efficient solver for integral flows in decision hypergraphs with applications to orthogonal knapsack problems. https://doi.org/10.1287/ijoc.2025.1692.cd, https://github.com/INFORMSJoC/2025.1692.Google Scholar
• Macedo R, Alves C, De Carvalho JV (2010) Arc-flow model for the two-dimensional guillotine cutting stock problem. Comput. Oper. Res. 37(6):991–1001.Crossref, Google Scholar
• Martin M, Morabito R, Munari P (2020a) A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem. Comput. Oper. Res. 115:104851.Crossref, Google Scholar
• Martin RK, Rardin RL, Campbell BA (1990) Polyhedral characterization of discrete dynamic programming. Oper. Res. 38(1):127–138.Link, Google Scholar
• Martin M, Birgin EG, Lobato RD, Morabito R, Munari P (2020b) Models for the two-dimensional rectangular single large placement problem with guillotine cuts and constrained pattern. Internat. Trans. Oper. Res. 27(2):767–793.Crossref, Google Scholar
• Morabito R, Pureza V (2010) A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem. Ann. Oper. Res. 179(1):297–315.Crossref, Google Scholar
• Morabito RN, Arenales MN, Arcaro VF (1992) An and—Or-graph approach for two-dimensional cutting problems. Eur. J. Oper. Res. 58(2):263–271.Crossref, Google Scholar
• Oliveira J, Ferreira J (1990) An improved version of Wang’s algorithm for two-dimensional cutting problems. Eur. J. Oper. Res. 44(2):256–266.Crossref, 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
• Sadykov R, Vanderbeck F (2013) Column generation for extended formulations. EURO J. Comput. Optim. 1(1):81–115.Crossref, Google Scholar
• Tange O (2023) Gnu parallel 20231122 (‘grindavík’). Accessed July 7, 2026, https://doi.org/10.5281/zenodo.10199085.Google Scholar
• Tschöke S, Holthöfer N (1995) A new parallel approach to the constrained two-dimensional cutting stock problem. Ferreira A, Rolim J, eds. Parallel Algorithms for Irregularly Structured Problems (Springer, Berlin), 285–300.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
• Velasco A, Uchoa E (2017) Improved space-state relaxation for constrained two-dimensional guillotine cutting problems. Technical Report No. L-2017-1, Cadernos do LOGIS-UFF, Niterói, Brazil.Google Scholar
• Viswanathan KV, Bagchi A (1993) Best-first search methods for constrained two-dimensional cutting stock problems. Oper. Res. 41(4):768–776.Link, Google Scholar
• Wang PY (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 (2025) EATKG: An open-source efficient exact algorithm for the two-dimensional knapsack problem with guillotine constraints. Eur. J. Oper. Res. 327(3):735–753.Crossref, Google Scholar
• Wei L, Lim A (2015) A bidirectional building approach for the 2d constrained guillotine knapsack packing problem. Eur. J. Oper. Res. 242(1):63–71.Crossref, Google Scholar
• Yoon K, Ahn S, Kang M (2013) An improved best-first branch-and-bound algorithm for constrained two-dimensional guillotine cutting problems. Internat. J. Production Res. 51(6):1680–1693.Crossref, Google Scholar