用图结构在线学习变量选择，提升混合整数规划求解速度。
Influence branching for learning to solve mixed-integer programs online
- 基于图结构的变量选择策略，通过在线优化确定最优分支顺序。
- 在SCIP上实现计算加速，性能媲美当前最先进方法。
- 适用于约束矩阵、目标系数等变化的通用在线求解场景。
在第20届混合整数规划研讨会的计算竞赛背景下，本文提出一种新的在线学习求解混合整数规划（MIP）的方法。引入了一种基于图结构的变量选择策略——影响分支（Influence branching），在整个分支定界算法的初始迭代中应用。该启发式策略通过汤普森采样在线优化，根据相对于SCIP的计算加速效果，筛选出最佳的图表示形式。实验结果表明，该方法性能与当前最先进的在线学习方法相当。此外，结果还显示，该方法在更通用的在线框架下具有良好的泛化能力，即使约束矩阵、约束向量和目标系数均存在变化，且样本量充足时仍表现良好。
原文摘要 · Abstract (English)
On the occasion of the 20th Mixed Integer Program Workshop's computational competition, this work introduces a new approach for learning to solve MIPs online. Influence branching, a new graph-oriented variable selection strategy, is applied throughout the first iterations of the branch and bound algorithm. This branching heuristic is optimized online with Thompson sampling, which ranks the best graph representations of MIP's structure according to computational speed up over SCIP. We achieve results comparable to state of the art online learning methods. Moreover, our results indicate that our method generalizes well to more general online frameworks, where variations in constraint matrix, constraint vector and objective coefficients can all occur and where more samples are available.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。