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.
Abstract
Mixed-Integer Linear Programming (MILP) is a fundamental problem class in operations research and combinatorial optimization, with broad applications to industrial decision-making. Owing to their NP-hardness, however, modern solvers may struggle to find high-quality solutions for challenging MILP instances within practical time limits. Recent learning-based approaches seek to accelerate MILP solving by directly predicting high-quality solutions from static instance-level features, such as variable-constraint bipartite graphs. Yet accurate solution prediction from instance features alone is difficult, and these methods largely overlook the information revealed during the solver's search process. In this paper, we find that solutions produced at the early search stage of MILP solvers, which are computationally cheap to obtain, are often structurally close to the solutions found after full-budget search. Motivated by this observation, we propose a new solver-informed paradigm that shifts the learning target from variable assignment to early-to-final consistency: for each variable, we predict whether its early-stage assignment should persist in full-budget solutions. The predicted consistency naturally guides downstream search, for instance by fixing the assignments deemed consistent. At inference time, we further ensemble consistency predictions across multiple early-stage solutions to improve robustness. Experiments across four MILP benchmarks show our method improves prediction-guided search across diverse downstream pipelines. With Gurobi, our proposed method reduces the primal gap by 56.9% on average and closes it completely on combinatorial auction instances. Besides, we transferred the Gurobi-trained model zero-shot to SCIP without adaptation, achieving a 36.4% average gap reduction across benchmarks.
This work proposes an LLM-guided cutting-plane management framework that removes dependence on domain-specific training data and substantially reduces reliance on expert-crafted configurations.
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.
Zherong Zhang, Guanli Li, Chengrui Gao et al.· 0 citations
Mixed-Integer Linear Programs (MIPs) are powerful and flexible tools for modeling a wide range of real-world combinatorial optimization problems. Predict-and-Search methods operate by using a predictive model to estimate promising variable assignments and then guiding a search procedure toward high-quality solutions. Recent research has demonstrated that incorporating machine learning (ML) into the Predict-and-Search framework significantly enhances its performance. Still, it is restricted to binary-only problems and overlooks the presence of fixed variables structure that commonly arise in real-world settings. 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. Experiments on several real-world large-scale problems demonstrate that ID-PaS+ consistently achieves superior performance compared to the state-of-the-art solver Gurobi and PaS.
Junyang Cai, El Mehdi Er Raqabi, Pascal Van Hentenryck et al.· Proceedings of the Internati...· 0 citations
Machine learning methods have shown that data-driven policies can accelerate mixed-integer linear programming (MILP) solvers, but many such approaches remain difficult to inspect, adapt, and deploy because the learned policy is represented as an external predictor or other opaque model. By contrast, explicit solver logic is easier to understand and integrate, but is usually hand-designed rather than learned from solver feedback. We study whether the automatic design of MILP solver logic can instead be cast as LLM-guided closed-loop search over executable white-box components evaluated directly by end-to-end solver behavior. To this end, we propose a closed-loop program evolution framework for MILP solver auto-design, implemented through PySCIPOpt, and instantiate it on the joint design of a cut selector and a branching rule. Candidate programs are iteratively generated, loaded into SCIP, and evaluated by direct execution on MILP instances, with the resulting feedback guiding performance-based selection, targeted repair, diagnostic reflection, and diversity-aware population maintenance. The method outputs explicit solver components that can be inspected, modified, and deployed within standard solver workflows. Across four benchmark families, we find that LLM-guided program evolution can discover competitive domain-specialized policies in several settings.
Jinbiao Nie, Kewei Feng, Xiaoyuan Zhang et al.· 0 citations
This letter proposes a learning method for real-time solution of receding-horizon mixed-integer nonlinear programs (RH MINLPs) in dynamic energy supply systems. Conventional MINLP solvers incur high computational costs. Although machine learning (ML) approximations can reduce the cost, existing approaches struggle to satisfy temporally coupled hard constraints solely through the forward pass, as required in industrial applications. To address this issue, we propose a two-stage architecture. First, RH MINLP is reformulated via backward recursion to decouple temporal dependencies into local allocation tasks. Second, a specialized neural network (NN) architecture embeds structural correction mechanisms into differentiable layers, thereby satisfying hard constraints during the forward pass without the need for external solvers. The proposed NN comprises a scalable binary-constraint layer and a continuous-allocation layer. A case study on a district cooling system demonstrates that the proposed method enables large-scale end-to-end training and generates feasible operational plans in real time.
Morimasa Okamoto, Yasuaki Wasa· IEEE Control Systems Letters· 0 citations