用图神经网络预测整数规划最优解，提升求解器决策效率
Learning optimal objective values for MILP
- 基于图神经网络和动态特征预测问题最优目标值
- 在多个基准测试中准确率显著高于现有方法
- 适合优化求解器开发者与运筹学研究者参考
现代混合整数线性规划（MILP）求解器通常采用分支定界算法，并结合大量辅助组件加速搜索。近年来，机器学习在增强这些算法组件方面发展迅速。本文提出一种预测最优目标值的方法，等价于判断当前候选解是否最优。为此，我们设计了一种基于图神经网络（GNN）的预测器，并引入一组动态特征。在多种基准测试上的实验结果表明，该方法在预测任务中表现出色，准确率显著优于现有方法。这些发现为将基于机器学习的预测集成到MILP求解器中提供了新契机，有助于实现更智能的决策和性能提升。
原文摘要 · Abstract (English)
Modern Mixed Integer Linear Programming (MILP) solvers use the Branch-and-Bound algorithm together with a plethora of auxiliary components that speed up the search. In recent years, there has been an explosive development in the use of machine learning for enhancing and supporting these algorithmic components. Within this line, we propose a methodology for predicting the optimal objective value, or, equivalently, predicting if the current incumbent is optimal. For this task, we introduce a predictor based on a graph neural network (GNN) architecture, together with a set of dynamic features. Experimental results on diverse benchmarks demonstrate the efficacy of our approach, achieving high accuracy in the prediction task and outperforming existing methods. These findings suggest new opportunities for integrating ML-driven predictions into MILP solvers, enabling smarter decision-making and improved performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。