Learning Early-to-Final Solution Consistency for MILP Acceleration

Guanlin Li; Chengrui Gao; Chenguang Wang; Haopu Shang; Zherong Zhang; Ke Xue; Jixiang Lu; Weiyong Yang

cs.AIAug 20, 2026

Learning Early-to-Final Solution Consistency for MILP Acceleration

Authors: Guanlin Li, Chengrui Gao, Chenguang Wang, Haopu Shang, Zherong Zhang, Ke Xue, Jixiang Lu, Weiyong Yang,

Organizations: State Key Laboratory of Novel SoftwareTechnology, Nanjing University · School of Artificial Intelligence,Nanjing University · State Key Laboratory of Technology and Equipment for Defense Against Power System Operational Risks, Nari Technology Co., Ltd.

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.

Figures & tables

Panel of Figure 1 — Figure 1: Evolution of the primal gap over the solving process with Gurobi (left) and SCIP (right) on set covering instances. The time axis is scaled to highlight the early phase $0\!-\!200\,\mathrm{s}$ . Results on other problem classes are provided in App. A .

Panel of Figure 2 — Figure 2: Distributions of flipped integer variables between early and full-budget solutions. ‘CA’ and ‘WA’ stand for combinatorial auction and workload apportionment, respectively.

	CA $\uparrow$ (BKS 98627.99)		SC $\downarrow$ (BKS 123.37)		WA $\downarrow$ (BKS 706.86)		IP $\downarrow$ (BKS 11.72)
Method	Obj	Gap	Obj	Gap	Obj	Gap	Obj	Gap
Gurobi (3600s)	98448.84	179.15	123.37	0.00	706.86	0.00	11.72	0.00
Gurobi (1000s)	97311.69	1316.30	123.64	0.27	707.36	0.50	13.77	2.05
ND	94340.63	4287.36	123.62	0.25	707.10	0.24	14.15	2.43
PS	97906.20	721.79	123.60	0.23	707.09	0.23	12.08	0.36
Apollo	98083.79	544.20	123.56	0.19	707.06	0.20	11.97	0.25

Table 1: Main results with Gurobi. Obj is the final feasible objective and Gap is the absolute gap to the in-study BKS. Arrows indicate the preferred objective direction; bold marks the best learning-based result or a positive gap reduction.

Figure 3: Average primal gap to the BKS versus time under a 1,000-second time limit. EnCore starts after the early solution collection. Each curve is shown only after all test instances have obtained a feasible solution.

Method	CA $\uparrow$	SC $\downarrow$	WA $\downarrow$	IP $\downarrow$
SCIP(1000s)	94701.91	127.99	709.06	23.49
ND	94342.12	125.14	707.33	18.19
PS	97097.46	125.03	708.49	17.02
Apollo	97335.92	124.97	708.43	16.21
EnCore-ND	96641.43	124.75	707.24	14.91
EnCore-PS	97707.64	125.04	708.22	16.13

Table 2: Zero-shot transfer from Gurobi to SCIP under a 1,000-second total budget. Bold marks the best result. The BKS is presented in Table 1 .

Variant	CA $\uparrow$	SC $\downarrow$	WA $\downarrow$	IP $\downarrow$
Predict-and-Search	97906.20	123.60	707.09	12.08
+ early solution as feature	98318.22	123.55	707.04	12.17
+ consistency prediction target	98616.65	123.53	706.99	11.90
+ early-solution ensemble	98627.99	123.50	706.98	11.95

Table 3: Ablation study of key components under the Predict-and-Search pipeline. Average objective values are reported.

Figure 4: Average final objective of EnCore-PS under different maximum early-solution collection times.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5: Primal gap versus solving time for Gurobi.

Panel of Figure 6 — Figure 6: Early-to-final flip distributions for Gurobi; red and green dashed lines denote the mean and median.

Panel of Figure 7 — Figure 7: Primal gap versus solving time for SCIP.

Panel of Figure 8 — Figure 8: Early-to-final flip distributions for SCIP; red and green dashed lines denote the mean and median.

Panel of Figure 9 — Figure 9: Solver behavior on the MIPLIB IIS dataset with Gurobi.

Index	Feature	Description
Variable-node features
0	Objective	Normalized objective coefficient.
1	Variable coefficient	Average variable coefficient across all constraints.
2	Variable degree	Degree of the variable node in the bipartite graph.
3	Maximum coefficient	Maximum variable coefficient across all constraints.
4	Minimum coefficient	Minimum variable coefficient across all constraints.

Appendix

Table 4: Graph features for input.

	CA	SC	IP	WA
Constraint Number	2590.33	3000	195	64306
Variable Number	1500	5000	1083	61000
Binary Variables Number	1500	5000	1050	1000
Continuous Variables Number	0	0	33	60000
Integer Variables Number	0	0	0	0

Appendix

Table 5: Statistical information of the benchmark instances.

Predictor	Downstream	Mean Obj $\downarrow$	Feas.
Origin	Neural Diving	243.00 †	3/11
EnCore	Neural Diving	173.45	11/11
Origin	Predict-and-Search	172.00	11/11
EnCore	Predict-and-Search	171.73	11/11
Origin	Apollo-MILP	172.91	11/11
EnCore	Apollo-MILP	172.82	11/11

Appendix

Table 6: Zero-shot cross-family transfer to the MIPLIB IIS subset. Mean Obj is the mean of the per-instance final objectives. Feas. reports the number of instances with a finite feasible objective. † means computed only over its three feasible instances.

	ND		PS		Apollo-MILP
Instance	GCN	Ours	GCN	Ours	GCN	Ours
ex1010-pi	–	242.00	237.00	236.00	241.00	238.00
fast0507	–	174.00	174.00	174.00	174.00	174.00
glass-sc	–	23.00	23.00	23.00	23.00	23.00
iis-glass-cov	–	21.00	21.00	21.00	21.00	21.00
iis-hc-cov	–	17.00	17.00	17.00	17.00	17.00

Appendix

Table 7: Final objectives on the eleven MIPLIB IIS instances. All instances are minimization problems. Bold marks the lowest objective in each row; a dash indicates that no finite feasible solution was found.

Benchmark	CA	SC	IP	WA
PS+Gurobi	$(600,0,20)$	$(2000,0,100)$	$(400,5,10)$	$(0,500,10)$
PS+SCIP	$(400,0,20)$	$(2000,0,100)$	$(400,5,1)$	$(0,600,5)$

Appendix

Table 8: The partial solution size parameters

(k_{0},k_{1})

and neighborhood parameter

\Delta

	CA	SC	IP	WA
Iteration 1	$(400,0,60)$	$(1000,0,200)$	$(100,20,50)$	$(20,200,100)$
Iteration 2	$(200,0,30)$	$(500,0,100)$	$(40,15,20)$	$(10,100,50)$
Iteration 3	$(100,0,15)$	$(250,0,50)$	$(20,15,10)$	$(10,5,5)$
Iteration 4	$(50,0,10)$	$(10,0,5)$	$(5,50,30)$	$(1,10,5)$

Appendix

Table 9: Hyperparameters

(k_{0}^{(i)},k_{1}^{(i)},\Delta^{(i)})

for Apollo-MILP.

Mixed-Integer Linear Programming

Mixed-integer linear programming (MILP) optimizes linear objectives and constraints when some decisions must be integer-valued.

See all 50 papers

Aug 26, 2026

SHSP: Structure-Aware Hierarchical Solution Prediction for Mixed-Integer Linear Programming

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, Guanlin Li, Chengrui Gao +5

State Key Laboratory of Novel Software Technology, Nanjing University · School of Artificial Intelligence, Nanjing University · State Key Laboratory of Technology and Equipment for Defense Against Power System Operational Risks, Nari Technology Co., Ltd.

Mixed-Integer Linear Programming Neural Combinatorial Optimization Autoregressive Decoding

Ask PDF

Sep 30, 2026

Reformulation-Contrastive Learning for Mixed Integer Programs

Mixed-integer linear programs (MILP) model many real-world decision problems, motivating machine-learning methods that exploit recurring structure to accelerate MILP solving. MILPs can admit many equivalent formulations: integrality-preserving changes of variables and the addition of redundant constraints can alter their formulations while preserving the optimization problem. We leverage these reformulations as a source of self-supervision for learning general-purpose representations of MILP variables and constraints. We characterize the affine reformulations that are valid for every input instance, and distinguish re-descriptions, which leave variables unchanged, from substitutions, which transform them predictably. Building on equivariant self-supervised learning, we introduce ReMILP (reformulation-contrastive MILP representation learning), which jointly trains a graph neural network and a hypernetwork to predict how variable embeddings transform under changes of variables. Without solver-derived labels, ReMILP learns representations that exhibit the intended invariance and equivariance on unseen problem classes. Across binary solution, constraint activity and integrality gap prediction, these representations carry task-relevant information when frozen and provide a useful initialization for fine-tuning.

Ousema Bouaneni, Mathis Le Bail, Clément Elliker +2

LIX (École Polytechnique, IP Paris, CNRS) · AMIAD (Agence Ministérielle pour l’IA de Défense)

Contrastive Learning Representation Learning Graph Representation Learning Self-Supervised Learning Mixed-Integer Linear Programming Equivariant Representation Learning

Ask PDF

Aug 16, 2025

LLM-Guided Evolution of Symbolic Acceleration Inequality Families for MILP

Integer programming (IP) is central to many combinatorial optimization tasks but remains challenging due to its NP-hard nature. A practical way to improve IP solvers is to manually design inequality families that exploit problem structure. However, this creative process requires deep expertise and has therefore been difficult to automate. Our proposed framework, Symbolic Acceleration via Generative Evolution (SAGE), automates symbolic discovery of acceleration inequality families at the modeling level. It reasons over a symbolic IP formulation and a natural language description of the problem to discover a reusable set of acceleration inequality families that can be instantiated for each problem instance. These acceleration inequality families are selected through empirical admissibility and impact screening rather than mathematical proofs. SAGE (i) initializes a population of candidate acceleration inequality families via an initializer agent that uses an LLM; (ii) it screens candidates for admissibility on a small development admissibility set for solution feasibility and the separation of the relaxation solution; and (iii) it iteratively refines the population of inequalities through evolutionary crossover and mutation agents. Across seven MILP benchmarks, SAGE reduces optimality gaps by up to

62.1\%

relative to baseline MILP formulations solved with a fixed time budget and reaches target gaps up to

5.51\times

faster according to shifted geometric mean speedup. Comprehensive ablations show its robustness across different LLM backends and across solvers and internal cut settings. Code: https://github.com/milad1378yz/sage

Milad Yazdani, Mahdi Mostajabdaveh, Samin Aref +1

Department of Electrical and Computer Engineering, University of British Columbia, Vancouver, BC, Canada · Huawei Technologies Canada, Burnaby, BC, Canada · Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, ON, Canada

Mixed-Integer Linear Programming Integer Linear Programming Large Language Model-Guided Optimization

Ask PDF

Abstract

Mixed-Integer Linear Programming

Explore similar work

SHSP: Structure-Aware Hierarchical Solution Prediction for Mixed-Integer Linear Programming

Reformulation-Contrastive Learning for Mixed Integer Programs

LLM-Guided Evolution of Symbolic Acceleration Inequality Families for MILP