无需训练数据，快速求解动态组合优化问题
Learning for Dynamic Combinatorial Optimization without Training Data
- 利用图结构随时间的相似性加速求解
- 在限时条件下比基线快3-60倍，解质量高
- 适合资源受限、实时变化的场景使用
我们提出DyCO-GNN，一种新型无监督学习框架，用于动态组合优化，仅需问题实例本身即可运行，无需额外训练数据。该方法通过挖掘时变图快照间的结构相似性，在保持解质量的同时加速优化过程。我们在动态最大割、最大独立集和旅行商问题上进行了评估，涵盖多种规模的数据集，结果表明在严苛与中等时间预算下均表现优异。DyCO-GNN持续优于基线方法，最快可提升3-60倍效率，充分展现了其在快速演化的资源受限环境中的实际有效性。
原文摘要 · Abstract (English)
We introduce DyCO-GNN, a novel unsupervised learning framework for Dynamic Combinatorial Optimization that requires no training data beyond the problem instance itself. DyCO-GNN leverages structural similarities across time-evolving graph snapshots to accelerate optimization while maintaining solution quality. We evaluate DyCO-GNN on dynamic maximum cut, maximum independent set, and the traveling salesman problem across diverse datasets of varying sizes, demonstrating its superior performance under tight and moderate time budgets. DyCO-GNN consistently outperforms the baseline methods, achieving high-quality solutions up to 3-60x faster, highlighting its practical effectiveness in rapidly evolving resource-constrained settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。