通过几何增强预训练，提升图组合优化模型对旅行商问题的求解能力。
On the Effectiveness of Pretraining for Graph Combinatorial Optimization
- 用旋转和轴反射进行图对比学习，学习结构不变特征。
- 在TSP1000上使路径长度减少6.57%，优于无预训练模型。
- 适合需要高效求解高维图优化问题的研究者与工程师。
本文提出一种针对路由类问题（如旅行商问题）设计的自监督预训练框架。通过结合几何增强（特定为旋转与轴反射）的图对比学习，迫使模型学习结构不变的表示及全局相对距离分布。实验表明，该预训练策略在多种问题规模下均优于非预训练模型。值得注意的是，混合增强策略在TSP1000上实现6.57%的路径长度改善，证明几何预训练是有效扩展神经求解器至高维实例的重要归纳偏置。
原文摘要 · Abstract (English)
This paper introduces a self-supervised pretraining framework for graph combinatorial optimization specifically designed to address the nature of routing problems like the Traveling Salesman Problem. By utilizing graph contrastive learning with geometric augmentations (specifically, rotations and axial reflections) the model is forced to learn invariant structural representations and global relative distance distributions. Results demonstrate that this pretraining strategy outperforms non-pretrained models across various problem scales. Notably, the hybrid strategy (combining rotation and reflection) achieved a 6.57% improvement in tour length for TSP1000, proving that geometric pretraining is an important inductive bias for effectively scaling neural solvers to high-dimensional instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。