An Efficient Solver for Integral Flows in Decision Hypergraphs with Applications to Orthogonal Knapsack Problems
TL;DR
A generic solver for computing integral flows in decision hypergraphs, subject to upper bound constraints on some hyperarcs, is proposed, which outperforms the best algorithm known thus far and is the first to close the optimality gap for all instances of several well-known benchmarks.
Abstract
We propose a generic solver for computing integral flows in decision hypergraphs, subject to upper bound constraints on some hyperarcs. This framework captures an entire class of cutting problems, including the guillotine two-dimensional knapsack problem (G2KP), which is our primary focus. The main contribution of our approach is the introduction of new generic valid inequalities and their effective inclusion into a labeling algorithm, using the concept of potentials. To manage the size of the formulation, we developed a hyperarc generation strategy that constructs only a relevant subset of the vertices and hyperarcs. The resulting speedup enables the efficient inclusion of our new valid inequalities in the solving process. Computational results on instances from the literature demonstrate the strength of our approach. Our solver outperforms the best algorithm known thus far and is the first to close the optimality gap for all instances of several well-known benchmarks. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1692 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1692 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .