Jul 2026· INFORMS journal on computing· 0 citations· 28 references
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/ .
It is proved that Minimal-to-Maximal Conversion Search is in fact not output-polynomial and the lower bound construction motivates a more detailed analysis of how certain heuristic choices in the algorithm design affect the running time.
Some equity constraints on the coloring classes of a classical coloring of the vertices of a graph give rise to the equitable coloring: the number of vertices colored with each color differs by at most one. The least number of colors for which a graph has such an equitable coloring is called the equitable chromatic number. In this paper a new integer programming model is introduced based on a stable set formulation for the decision version of the Equitable Coloring Problem. This new formulation is integrated into two Binary Search-like algorithms, the efficiency of which we have tested on thirty-two instances from literature. The numerical results show that this new approach was able to improve the known lower bounds of equitable chromatic number for two thirds of the tested instances and found the equitable coloring number for two instances.
History: Accepted by Andrea Lodi, 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.1294 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1294 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
E. F. Olariu, C. Frăsinaru· INFORMS journal on computing· 0 citations
Exact algorithms for solving mixed-integer bilevel linear programs (MIBLPs) typically rely on sequences of lower and upper bounds that converge to the optimal value. These procedures are commonly initialized using the single-level relaxation (SLR), obtained by omitting the follower's optimality condition and solving the resulting single-level optimization problem. In this paper, we investigate whether, for broad classes of MIBLPs, the resulting standard bounds admit uniform improvements that can be computed within the same computational complexity regime. For pure continuous bilevel linear programs, we show that, unless $P = NP$, neither the SLR-based lower bound nor its associated upper bound can be uniformly improved in polynomial time, even for the class of min-max problems. We then extend this analysis to the class of pure integer min-max bilevel linear programs under the assumption that the polynomial hierarchy does not collapse. First, we show that the continuous relaxation of the SLR admits no uniform polynomial-time computable improvement. We then prove that neither the SLR itself nor its associated upper bound admits a uniform improvement by a polynomial-time algorithm with access to a mixed-integer linear programming (MILP) oracle. Importantly, this rules out uniform improvements by iterative MILP-based approaches, including cutting-plane-based and decomposition algorithms. Overall, our results demonstrate that the SLR-based bounds are, in a complexity-theoretic sense, unimprovable systematically within their natural computational regimes.
A unified Parallel Evolutionary Algorithm Framework (PEAF) is proposed, which combines structure-inheriting crossover operators, a hierarchical mutation mechanism based on the Multiple Mutation Heuristic and the Auxiliary Cut Mutation Heuristic, and a diversity-preserving selection strategy.
Based on recent advances in Benders decomposition and two-stage stochastic integer programming, we present a framework to generate Lagrangian cuts in multistage stochastic mixed-integer linear programming by solving normalized dual problems. This framework can be incorporated into existing solution methods, such as stochastic dual dynamic integer programming. We show how different normalizations can be applied in order to generate cuts satisfying specific properties with respect to the convex hull of the epigraph of the value functions (e.g., having a maximum depth or being facet defining). We provide computational results to evaluate the efficacy and performance of this approach, showing that compared with existing techniques from the literature, significantly better lower bounds can be obtained.
History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.
Funding: The research of C. Füllner was funded by the Deutsche Forschungsgemeinschaft [Grant 445857709]. A research visit of C. Füllner at the Georgia Institute of Technology was funded by the Karlsruhe House of Young Scientists. The research of X. A. Sun was partially funded by the National Science Foundation [CAREER Award 2316675].
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.2024.1039 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.1039 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
Christian Füllner, X. A. Sun, Steffen Rebennack· INFORMS journal on computing· 1 citation· ⚡1
The length-constrained cycle partition problem (LCCP) is a graph optimization problem in which a set of nodes must be partitioned into a minimum number of cycles. Every node is associated with a critical time and the length of every cycle must not exceed the critical time of any node in the cycle. We formulate LCCP as a set partitioning model and solve it using an exact branch-price-and-cut approach. Our dynamic programming-based pricing algorithm to generate improving cycles exploits the particular structure of the pricing problem for efficient bidirectional search and symmetry breaking. Computational results show that the LP relaxation of the set partitioning model produces very strong dual bounds and our branch-price-and-cut method improves significantly over the state of the art. It is able to solve previously solved instances in a fraction of the time and closes 14 previously unsolved instances with numerically safe bounds, one of which has 76 nodes, a notable improvement over the previous limit of 52 nodes.
Mohammed Ghannam, Ambros M. Gleixner, Gioni Mexi et al.· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
