The Structure-Aware Hierarchical Solution Prediction (SHSP) framework is proposed that replaces the parallel marginal decoding of one-shot methods with a novel hierarchical conditional decoding mechanism and significantly outperforms existing one-shot prediction baselines.
Abstract
Mixed-Integer Linear Programming (MILP) is a fundamental optimization paradigm in combinatorial optimization and has been widely applied across real-world domains. Due to its NP-hard nature, obtaining optimal solutions for large-scale or highly constrained MILP instances remains computationally prohibitive. Learning-based solution prediction has therefore emerged as a promising approach to provide high-quality variable assignment for solver acceleration. However, existing methods typically adopt a one-shot prediction paradigm that predicts the marginal probabilities of all variables simultaneously. As a result, the conditional dependencies among variables are only implicitly captured through message passing, with the burden of modeling the combinatorial structure falling entirely on the representational capacity of graph neural networks. To address this limitation, we propose the Structure-Aware Hierarchical Solution Prediction (SHSP) framework that replaces the parallel marginal decoding of one-shot methods with a novel hierarchical conditional decoding mechanism. Specifically, SHSP constructs a variable coupling graph from the constraint structure, decodes variables sequentially along a hierarchy of increasing coupling strength, and conditions each hierarchy on previously predicted assignments. To mitigate error accumulation during the decoding process, SHSP further incorporates a confidence-aware mask-and-repair mechanism to identify and correct unreliable intermediate predictions. We integrate SHSP with multiple learning-guided search methods, and evaluate it on four standard MILP benchmarks. Experimental results demonstrate that SHSP significantly outperforms existing one-shot prediction baselines, achieving a 54% average reduction in solution gap.
This paper finds that solutions produced at the early search stage of MILP solvers are often structurally close to the solutions found after full-budget search, and proposes a new solver-informed paradigm that shifts the learning target from variable assignment to early-to-final consistency.
Guanli Li, Chengrui Gao, Chenguang Wang et al.· 0 citations
This work extends the current Predict-and-Search (PaS) framework to parametric general MIPs and introduces ID-PaS+, an identity-aware learning framework that enables the ML model to handle heterogeneous variables more effectively.
Junyang Cai, El Mehdi Er Raqabi, Pascal Van Hentenryck et al.· Proceedings of the Internati...· 0 citations
Graph4BiLO is introduced, a graph neural network (GNN) approach for learning bilevel value functions from variable--constraint graph representations that obtains objective values comparable to Neur2BiLO across all tested sizes while avoiding size-specific neural networks.
Jessica D. Elrefaei, Kaixun Hua, Seungbae Kim et al.· 0 citations
The shortest path problem (SPP) with constraints constitutes a fundamental yet computationally prohibitive NP-hard challenge in operations research and logistics. Traditional optimization algorithms, including both exact and approximate methods, often suffer from prohibitive computational times and severe scalability bottlenecks on large-scale instances. In contrast, emerging Neural Combinatorial Optimization (NCO) approaches offer the potential for rapid inference but frequently fail to guarantee structural feasibility under strict constraints. To bridge this gap, this study introduces E2E_GERL, a novel end-to-end graph-embedded reinforcement learning algorithm for the time-constrained SPP. The problem is reformulated as a structure-aware and resource-aware sequential decision-making process, where a neural graph embedding network, structure2vec, is integrated to capture the long-term structural equivalence of critical graph nodes. In our framework, a ReLU-based Lagrangian penalty is introduced to embed time constraint violation into the learning objective, and n-step Q-learning is employed to effectively overcome delayed path-level consequences. Extensive experiments on synthetic graphs, modified benchmark instances, and a real-world logistics network demonstrate the superiority of the proposed algorithm, E2E_GERL. It achieves better results with substantially lower inference time than classical and NCO baselines, which also validate the potential of integrating NCO into constrained optimization problem algorithms.
Shu-Hao Yang, Min Huang, Shengxiang Yang et al.· Mathematics· 0 citations
A solver-informed diagnosis mechanism that exploits fine-grained solver statistics as verbal gradients for targeted refinement and a structured memory abstracts prior experience into reusable modeling strategies, avoiding redundant exploration while enabling zero-shot transfer to unseen problems and bootstrapping smaller LLMs.
Haofeng Yuan, Ji-Ming Peng, Jieyi Bi et al.· 0 citations
Sequential reinforcement learning (RL) solvers and global diffusion model (DM) solvers for neural combinatorial optimization exhibit complementary failure modes under an optimization-regret view. The former enjoys small marginal regret in the early construction stage, but suffers from horizon-wise compounding errors with super-linear regret growth; the latter avoids horizon compounding but incurs linear or sublinear regret w.r.t. the dimension of the remaining unsolved subspace. We propose Hybrid Neural Solver for Combinatorial Optimization (HyCO), a hybrid inference algorithm that constructs a solution prefix with an RL solver and adaptively switches to a conditional DM to complete the remaining decisions. To characterize why such hybridization helps, when to trigger the handover, and how to realize it in practice, we first develop a unified error-scaling theoretical framework and prove that, under explicit error-scaling assumptions, i) the hybrid structure achieves strictly lower expected regret than either backbone alone, and ii) there exists a unique optimal trigger step that minimizes the hybrid regret. We then design a lightweight adaptive trigger that combines policy entropy and RL-DM disagreement to detect trajectory-level signals of the regime shift as a practical proxy, since the optimal trigger step is defined at the expected-regret level and is not directly computable on individual trajectories. Experimental results on diverse benchmarks demonstrate that HyCO achieves consistent improvements over both backbones and support the empirical effectiveness of adaptive triggering.
Yuheng Li, Di Yang, Haipeng Chen et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
