用稀疏学习加速整数规划求解器，效果媲美深度模型却只需极少参数和算力。
Speeding Up Mixed-Integer Programming Solvers with Sparse Learning for Branching
- 采用稀疏学习构建轻量级分支评分模型，参数少于顶尖图神经网络的4%。
- 在多种问题上比默认求解器更快，且无需GPU即可超越GPU加速的深度模型。
- 训练部署简单，小数据集下仍有效，适合资源受限场景。
机器学习正被用于改进混合整数规划的分支定界算法决策。现有方法多依赖深度学习，需大规模训练数据和大量计算资源，通常需GPU并行。本文另辟蹊径，提出可解释的轻量级模型，专注于近似强分支（SB）评分——一种高效但计算开销大的分支规则。通过稀疏学习，模型参数不足先进图神经网络（GNN）的4%，却达到相当准确率。相比SCIP内置分支规则及基于GNN的模型，本方法仅用CPU即实现更快求解速度，且优于使用GPU加速的GNN。模型训练与部署简便，在小规模训练集下依然有效，适用于低资源环境。跨多样化问题类别的实验验证了该方法的高效性。
原文摘要 · Abstract (English)
Machine learning is increasingly used to improve decisions within branch-and-bound algorithms for mixed-integer programming. Many existing approaches rely on deep learning, which often requires very large training datasets and substantial computational resources for both training and deployment, typically with GPU parallelization. In this work, we take a different path by developing interpretable models that are simple but effective. We focus on approximating strong branching (SB) scores, a highly effective yet computationally expensive branching rule. Using sparse learning methods, we build models with fewer than 4% of the parameters of a state-of-the-art graph neural network (GNN) while achieving competitive accuracy. Relative to SCIP's built-in branching rules and the GNN-based model, our CPU-only models are faster than the default solver and the GPU-accelerated GNN. The models are simple to train and deploy, and they remain effective with small training sets, which makes them practical in low-resource settings. Extensive experiments across diverse problem classes demonstrate the efficiency of this approach.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。