用图神经网络筛选关键约束，让割平面生成更快更强。
Learn2Aggregate: Supervised Generation of Chvátal-Gomory Cuts Using Graph Neural Networks
- 训练图神经网络识别可聚合的有用约束，实现稀疏聚焦。
- 在最大测试集上减少75%约束，性能提升至标准方法两倍，提速40%。
- 适合求解大规模混合整数规划问题的研究者与工程师。
我们提出《Learn2Aggregate》，一种用于优化混合整数线性规划（MILP）中Chvátal-Gomory（CG）割生成的机器学习框架。该框架训练图神经网络以分类可用于聚合的有用约束。基于机器学习的CG分离器仅聚焦少数关键约束，显著提升求解速度，同时不牺牲生成割的强度。核心在于将约束分类任务设计为鼓励稀疏聚合，符合实证发现。结合精心设计的约束标注方案与深度学习和特征工程的混合策略，本方法在五个不同类型的MILP基准测试中均表现更优。在最大测试集上，该方法解决的整数间隙约为标准方法的两倍，且运行速度快40%。这一提升得益于在聚合前剔除了75%的约束。
原文摘要 · Abstract (English)
We present $\textit{Learn2Aggregate}$, a machine learning (ML) framework for optimizing the generation of Chvátal-Gomory (CG) cuts in mixed integer linear programming (MILP). The framework trains a graph neural network to classify useful constraints for aggregation in CG cut generation. The ML-driven CG separator selectively focuses on a small set of impactful constraints, improving runtimes without compromising the strength of the generated cuts. Key to our approach is the formulation of a constraint classification task which favours sparse aggregation of constraints, consistent with empirical findings. This, in conjunction with a careful constraint labeling scheme and a hybrid of deep learning and feature engineering, results in enhanced CG cut generation across five diverse MILP benchmarks. On the largest test sets, our method closes roughly $\textit{twice}$ as much of the integrality gap as the standard CG method while running 40$% faster. This performance improvement is due to our method eliminating 75% of the constraints prior to aggregation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。