MILP 풀이에서 '초반에 나온 답'을 믿어도 되는지를 학습시켜 최적화 속도를 크게 높였다
arXiv:2608.199532026-08-21
Learning Early-to-Final Solution Consistency for MILP Acceleration
MILP 풀이에서 '초반에 나온 답'을 믿어도 되는지를 학습시켜 최적화 속도를 크게 높였다
혼합정수계획법(MILP)은 물류, 스케줄링 등에 널리 쓰이지만 어려운 문제는 풀이 시간이 매우 오래 걸린다. 이 연구는 솔버가 초반에 빠르게 찾아낸 임시 해답이 최종 정답과 상당 부분 일치한다는 점에 착안해, '이 변수 값이 최종까지 유지될지'를 예측하는 방식(EnCore)을 제안했다. Gurobi 기준 기존 방법 대비 평균 56.9% 성능 격차를 줄였고, 다른 솔버(SCIP)에 재학습 없이 옮겨도 36.4% 개선 효과가 유지됐다.
METAL MEDIA 해설 도표
MILP 풀이에서 '초반에 나온 답'을 믿어도 되는지를 학습시켜 최적화 속도를 크게 높였다
01MILP는 변수 중 일부가 정수여야 하는 최적화 문제로, 어려운 경우 유명 솔버(Gurobi, SCIP 등)로도 정해진 시간 안에 좋은 답을 찾기 힘들다.
02기존 AI 기반 가속 방법들은 문제의 구조 정보만 보고 처음부터 완전한 해답을 예측하려 했는데, 이는 매우 어려운 과제였다.
03연구팀은 솔버가 짧게 돌려서 얻은 '초기 해'가 오래 돌린 뒤의 '최종 해'와 변수 값이 대부분(예: 워크로드 분배 문제에서 95.63%) 같다는 사실을 발견했다.
04그래서 완전한 해를 새로 예측하는 대신, 초기 해의 각 변수 값이 '최종까지 그대로 유지될지 아닌지'만 예측하도록 학습 목표를 바꿨다. 이렇게 하면 신뢰할 만한 값은 고정하고, 불확실한 소수의 변수에만 탐색을 집중시킬 수 있다.
05추론 시에는 초기 단계에서 나온 여러 개의 후보 해를 종합(앙상블)해 예측을 더 안정적으로 만들었고, Gurobi 기준 조합경매(combinatorial auction) 문제에서는 정답과의 격차를 완전히 없앴다.
METAL MEDIA이 원문을 바탕으로 재구성한 해설 도표이며, 논문 저자의 원문 figure가 아닙니다.
무엇을 했나
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 속도를 높이는 기존 방법들.
