Learning Early-to-Final Solution Consistency for MILP Acceleration
arXiv:2608.199532026-08-21
Teaching AI to judge which early guesses in optimization problems will stay correct, to speed up solvers
Mixed-Integer Linear Programming (MILP) underlies many industrial decisions but hard instances can take solvers a very long time. This paper shows that solutions found early by a solver already agree with the final solution on most variables, and proposes EnCore, which predicts whether each early variable assignment will persist rather than predicting a full solution from scratch. With Gurobi, this cut the gap to the best-known solution by 56.9% on average, and the trained model still cut the gap by 36.4% when transferred without retraining to a different solver, SCIP.
What they did
MILP problems require some variables to be integers, and hard instances remain difficult even for advanced solvers like Gurobi and SCIP within practical time limits.
Prior learning-based acceleration methods tried to predict a complete solution directly from the problem's static structure, which is a very hard learning task.
The authors found that a solution obtained early in a solver's run already matches the final full-budget solution on most variables (e.g., 95.63% agreement on workload apportionment instances).
Instead of predicting the full solution, EnCore predicts, for each variable, whether its early value will remain unchanged in the final solution — an easier task that lets the search focus effort on the smaller set of unresolved variables.
At inference time, predictions from several early candidate solutions are combined (ensembled) for robustness, and on combinatorial auction instances the method fully closed the gap to the best-known solution under Gurobi.
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 −200s. Results on other problem classes are provided in App. A.
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.
CA ↑ (BKS 98627.99)
SC ↓ (BKS 123.37)
WA ↓ (BKS 706.86)
IP ↓ (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
EnCore-ND
97847.92
780.70
123.58
0.21
707.03
0.17
13.47
1.75
EnCore-PS
98627.99
0.00
123.50
0.13
706.98
0.12
11.95
0.23
EnCore-Apollo
98491.40
136.59
123.57
0.20
707.03
0.17
11.82
0.10
Best Gap Reduction
721.79
100.0%
0.10
43.5%
0.11
47.8%
0.15
60.0%
Figure 2: Distributions of flipped integer variables between early and full-budget solutions. ‘CA’ and ‘WA’ stand for combinatorial auction and workload apportionment, respectively.
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.
Method
CA ↑
SC ↓
WA ↓
IP ↓
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
EnCore-Apollo
97293.51
125.38
707.91
17.39
Best Gap Reduction
53.6%
22.0%
33.1%
50.7%
(b) Gurobi on WA
Table 3: Ablation study of key components under the Predict-and-Search pipeline. Average objective values are reported.
Variant
CA ↑
SC ↓
WA ↓
IP ↓
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
(c) SCIP on CA
Table 4: Graph features for input.
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.
5
Variable type
Indicator of whether the variable is integer.
6–17
Position embedding
Binary encoding of the variable’s order among all variables.
18
Early-solution value
Value of the variable in the early solution collected as described in Appendix C.
Constraint-node features
0
Constraint coefficient
Average of the nonzero coefficients in the constraint.
1
Constraint degree
Degree of the constraint node in the bipartite graph.
2
Bias
Normalized right-hand side of the constraint.
3
Sense
Sense of the constraint.
Edge features
0
Coefficient
Coefficient connecting the constraint and variable nodes.
(d) SCIP on WA
Table 5: Statistical information of the benchmark instances.
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
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.
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.
Predictor
Downstream
Mean Obj ↓
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
Figure 4: Average final objective of EnCore-PS under different maximum early-solution collection times.
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.
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
ramos3
–
235.00
229.00
226.00
231.00
233.00
scpj4scip
132.00
132.00
132.00
132.00
132.00
132.00
scpk4
328.00
330.00
326.00
327.00
330.00
330.00
scpl4
269.00
269.00
269.00
269.00
269.00
269.00
seymour
–
423.00
423.00
423.00
423.00
423.00
v150d30-2hopcds
–
42.00
41.00
41.00
41.00
41.00
(b) SC
Table 8: The partial solution size parameters (k0,k1) and neighborhood parameter Δ.
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)
(d) IP
Table 9: Hyperparameters (k0(i),k1(i),Δ(i)) for Apollo-MILP.
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)
(b) SC
Why it matters
MILP optimization drives real-world decisions like logistics, production planning, and network design, and this method can be layered onto existing AI-based solvers and transferred across different solver software without retraining, which matters for practical deployment. Reframing the learning task from 'build the whole answer' to 'judge what to trust' also offers a genuinely different and lower-difficulty way to approach the problem.
(d) IP
Terms in this paper
MILP (Mixed-Integer Linear Programming) · An optimization problem where some variables must be whole numbers, used in scheduling, logistics, and more.
branch-and-bound · The core search method solvers use, splitting the solution space and pruning bad branches to find optimal answers.
primal gap · The difference between the best solution found so far and the best known solution; smaller means closer to optimal.
graph neural network (GNN) · A neural network that learns from a graph representation of variables and constraints in the MILP.
Predict-and-Search / Neural Diving · Existing methods that use AI predictions to fix some variables or shrink the search space to speed up solvers.
(b) Aggregate flip distribution.
Original abstract (English)
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.
