EUVIMEDEUVIMED entdecken
Crossref

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

Arthur Léonard, François Clautiaux

INFORMS Journal on Computing · 16.07.2026

DOI: 10.1287/ijoc.2025.1692 ↗

Kurz gefasst

Fachartikel in der Zeitschrift INFORMS Journal on Computing, online erschienen am 16.07.2026. Verfasst von Arthur Léonard und 1 weiteren Autor:innen. Die Arbeit nennt 40 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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/ .

Zitieren

APA

Léonard, A., & Clautiaux, F. (2026). An Efficient Solver for Integral Flows in Decision Hypergraphs with Applications to Orthogonal Knapsack Problems. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2025.1692

Vancouver

Léonard A, Clautiaux F. An Efficient Solver for Integral Flows in Decision Hypergraphs with Applications to Orthogonal Knapsack Problems. INFORMS Journal on Computing. 2026. doi:10.1287/ijoc.2025.1692

BibTeX
@article{Lonard2026,
  author = {Léonard, Arthur and Clautiaux, François},
  title = {An Efficient Solver for Integral Flows in Decision Hypergraphs with Applications to Orthogonal Knapsack Problems},
  journal = {INFORMS Journal on Computing},
  year = {2026},
  doi = {10.1287/ijoc.2025.1692}
}
Kostenlos starten →