Learning Early-to-Final Solution Consistency for MILP Acceleration
arXiv:2608.199532026-08-21
MILP 풀이에서 '초반에 나온 답'을 믿어도 되는지를 학습시켜 최적화 속도를 크게 높였다
혼합정수계획법(MILP)은 물류, 스케줄링 등에 널리 쓰이지만 어려운 문제는 풀이 시간이 매우 오래 걸린다. 이 연구는 솔버가 초반에 빠르게 찾아낸 임시 해답이 최종 정답과 상당 부분 일치한다는 점에 착안해, '이 변수 값이 최종까지 유지될지'를 예측하는 방식(EnCore)을 제안했다. Gurobi 기준 기존 방법 대비 평균 56.9% 성능 격차를 줄였고, 다른 솔버(SCIP)에 재학습 없이 옮겨도 36.4% 개선 효과가 유지됐다.
무엇을 했나
MILP는 변수 중 일부가 정수여야 하는 최적화 문제로, 어려운 경우 유명 솔버(Gurobi, SCIP 등)로도 정해진 시간 안에 좋은 답을 찾기 힘들다.
기존 AI 기반 가속 방법들은 문제의 구조 정보만 보고 처음부터 완전한 해답을 예측하려 했는데, 이는 매우 어려운 과제였다.
연구팀은 솔버가 짧게 돌려서 얻은 '초기 해'가 오래 돌린 뒤의 '최종 해'와 변수 값이 대부분(예: 워크로드 분배 문제에서 95.63%) 같다는 사실을 발견했다.
그래서 완전한 해를 새로 예측하는 대신, 초기 해의 각 변수 값이 '최종까지 그대로 유지될지 아닌지'만 예측하도록 학습 목표를 바꿨다. 이렇게 하면 신뢰할 만한 값은 고정하고, 불확실한 소수의 변수에만 탐색을 집중시킬 수 있다.
추론 시에는 초기 단계에서 나온 여러 개의 후보 해를 종합(앙상블)해 예측을 더 안정적으로 만들었고, Gurobi 기준 조합경매(combinatorial auction) 문제에서는 정답과의 격차를 완전히 없앴다.
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
왜 중요한가
MILP 최적화는 물류, 생산계획, 통신망 설계 등 산업 현장의 의사결정에 폭넓게 쓰이는데, 이 방법은 기존 AI 가속 기법 위에 얹어 쓸 수 있고 다른 솔버로도 재학습 없이 옮길 수 있어 실용성이 크다. 완전한 해를 처음부터 만드는 대신 '이미 나온 답을 믿을지 말지'만 판단하게 함으로써 학습 난이도를 낮췄다는 점에서 문제 해결 접근 자체가 새롭다.
(d) IP
이 논문의 용어
MILP(혼합정수계획법) · 일부 변수가 정수여야 하는 선형 최적화 문제. 스케줄링, 물류 등에 쓰인다.
브랜치앤바운드 · 가능한 해의 공간을 나누고 가지치기하며 최적해를 찾는 MILP solver의 기본 탐색 방법.
primal gap · 현재 찾은 해와 알려진 최선의 해 사이의 격차. 작을수록 좋은 해에 가깝다는 뜻.
그래프 신경망(GNN) · 변수와 제약조건을 노드로 표현한 그래프를 입력받아 패턴을 학습하는 인공신경망 구조.
Predict-and-Search / Neural Diving · AI 예측값으로 일부 변수를 고정하거나 탐색 범위를 줄여 solver 속도를 높이는 기존 방법들.
(b) Aggregate flip distribution.
논문 원문 초록 (영문)
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.
