用无监督GNN压缩路径生成中的难题，提速求解并提升结果
Graph Reduction with Unsupervised Learning in Column Generation: A Routing Application
- 用无监督GNN自动筛选关键边，缩小路径定价问题规模
- 在固定预算下，大实例目标值提升超9%，收敛更快
- 方法可泛化到不同车型路径问题，适合大规模优化场景
列生成（CG）是解决大规模组合优化问题的常用方法，通过求解定价问题减少决策变量数量。对许多组合优化问题，定价问题为带资源约束的最短路径问题（ESPPRC）。大规模ESPPRC难以高效求解至近优解。为此，本文引入图神经网络（GNN）对ESPPRC进行无监督学习下的图缩减，使问题规模缩小至可用标准算法求解。该GNN输出保留边的概率分布，再通过局部搜索快速找到具有高简化成本的列，加速算法收敛。我们在带时间窗的容量车辆路径问题（CVRPTW）上测试，相比现有简化技术，显著提升收敛速度；在固定计算预算下，大实例的目标值提升超过9%。同时评估了算法性能，并验证方法在不同实例类型上的泛化能力。
原文摘要 · Abstract (English)
Column Generation (CG) is a popular method dedicated to enhancing computational efficiency in large scale Combinatorial Optimization (CO) problems. It reduces the number of decision variables in a problem by solving a pricing problem. For many CO problems, the pricing problem is an Elementary Shortest Path Problem with Resource Constraints (ESPPRC). Large ESPPRC instances are difficult to solve to near-optimality. Consequently, we use a Graph neural Network (GNN) to reduces the size of the ESPPRC such that it becomes computationally tractable with standard solving techniques. Our GNN is trained by Unsupervised Learning and outputs a distribution for the arcs to be retained in the reduced PP. The reduced PP is solved by a local search that finds columns with large reduced costs and speeds up convergence. We apply our method on a set of Capacitated Vehicle Routing Problems with Time Windows and show significant improvements in convergence compared to simple reduction techniques from the literature. For a fixed computational budget, we improve the objective values by over 9\% for larger instances. We also analyze the performance of our CG algorithm and test the generalization of our method to different classes of instances than the training data.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。