Learning Early-to-Final Solution Consistency for MILP Acceleration

arXiv:2608.199532026-08-21

让AI学会判断求解早期得到的答案哪些能保留到最后,从而加速混合整数规划求解

混合整数线性规划(MILP)广泛用于物流、排产等工业决策,但困难实例即使用先进求解器也很难在合理时间内求得高质量解。本文发现求解器在早期阶段快速得到的解,与经过完整时间求解后的最终解在大多数变量上是一致的,于是提出EnCore方法:不再从零预测完整解,而是预测每个变量的早期取值是否会保留到最终解。在Gurobi上该方法平均将与已知最优解的差距缩小了56.9%,且在未重新训练的情况下迁移到SCIP求解器仍能缩小36.4%的差距。

他们做了什么

MILP问题要求部分变量取整数,困难实例即便用Gurobi、SCIP等主流求解器,在实际时间限制内也常常难以求得优质解。
以往基于学习的加速方法试图仅凭问题的静态结构特征直接预测完整解,这是一项非常困难的学习任务。
研究者发现,求解器在早期阶段得到的解已经与最终完整求解得到的解在大多数变量上一致(例如在工作量分配问题中一致率达95.63%)。
因此EnCore不再重新预测完整解,而是针对每个变量预测其早期取值是否会保持到最终解,这样学习任务更聚焦,搜索也能集中在少数尚未确定的变量上。
推理时集成多个早期候选解的预测结果以提升鲁棒性,在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%

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

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.

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

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)

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)

为什么重要

MILP优化广泛应用于物流、生产排程、网络设计等工业决策场景,该方法可以叠加在现有AI加速方案之上,并且能在不重新训练的情况下迁移到不同的求解器软件,具有较强的实用价值。把学习目标从从零构建完整解转变为判断哪些早期结果可信,是一种降低学习难度的新思路。

本文术语

MILP(混合整数线性规划) · 部分变量必须取整数的线性优化问题,常用于排程、物流等场景。
分支定界法 · 求解器的核心搜索方法,通过划分解空间并剪枝来寻找最优解。
primal gap(原始间隙) · 当前所得解与已知最优解之间的差距,数值越小说明解越接近最优。
图神经网络(GNN) · 以变量和约束构成的图作为输入进行学习的神经网络结构。
Predict-and-Search / Neural Diving · 利用AI预测结果固定部分变量或缩小搜索空间来加速求解器的现有方法。

论文原文摘要（英文）

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.

作者 · Guanlin Li, Chengrui Gao, Chenguang Wang, Haopu Shang, Zherong Zhang, Ke Xue, Jixiang Lu, Weiyong Yang, Chao Qian

在 arXiv 阅读

METAL LAB 最新报道

图片来源： Guanlin Li et al., arXiv:2608.19953, CC BY 4.0

Learning Early-to-Final Solution Consistency for MILP Acceleration

他们做了什么

为什么重要

本文术语

最新论文

METAL LAB 最新报道