用智能选择器搭配多个神经求解器,让组合优化更准更快。
Neural Solver Selection for Combinatorial Optimization
- 根据问题特征自动选最合适的神经求解器
- 在TSPLIB和CVRPLIB上优化差距降低0.88%和0.71%
- 适合需要高精度的组合优化场景
机器学习在求解NP难组合优化问题中日益普及,催生了表现优异的神经求解器,即使缺乏领域知识也能有效工作。目前已有多种开源神经求解器,各自具有不同的设计动机和归纳偏置。我们发现现有求解器在不同实例上表现互补,提示通过实例级协调可显著提升性能。本文提出首个通用神经求解器协调框架,包含特征提取、选择模型与策略,旨在为每个实例分配最优求解器。我们选取多个性能领先的神经求解器作为候选,探索各组件的不同实现方式。在旅行商问题(TSP)和带容量约束车辆路径问题(CVRP)上评估,结果表明该框架能有效分发实例,复合求解器相比最佳单一求解器性能显著提升(如在TSPLIB上优化差距降低0.88%,在CVRPLIB上降低0.71%),且额外计算开销极小。
原文摘要 · Abstract (English)
Machine learning has increasingly been employed to solve NP-hard combinatorial optimization problems, resulting in the emergence of neural solvers that demonstrate remarkable performance, even with minimal domain-specific knowledge. To date, the community has created numerous open-source neural solvers with distinct motivations and inductive biases. While considerable efforts are devoted to designing powerful single solvers, our findings reveal that existing solvers typically demonstrate complementary performance across different problem instances. This suggests that significant improvements could be achieved through effective coordination of neural solvers at the instance level. In this work, we propose the first general framework to coordinate the neural solvers, which involves feature extraction, selection model, and selection strategy, aiming to allocate each instance to the most suitable solvers. To instantiate, we collect several typical neural solvers with state-of-the-art performance as alternatives, and explore various methods for each component of the framework. We evaluated our framework on two extensively studied combinatorial optimization problems, Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP). Experimental results show that the proposed framework can effectively distribute instances and the resulting composite solver can achieve significantly better performance (e.g., reduce the optimality gap by 0.88\% on TSPLIB and 0.71\% on CVRPLIB) than the best individual neural solver with little extra time cost.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。