通过测试时搜索提升神经图粗化模型的切割质量，显著减少对偶间隙。
Test-Time Search in Neural Graph Coarsening Procedures for the Capacitated Vehicle Routing Problem
- 引入随机边选择替代贪心策略，增强解的多样性。
- 在随机生成实例上，对偶间隙降低超过15%。
- 首次发现难识别的框架容量不等式，适合优化求解器研究者。
识别有效不等式（如舍入容量不等式RCIs）是求解容量车辆路径问题（CVRP）割平面方法的关键。尽管基于深度学习的分离方法能学习到高质量切割，但分析表明其生成的切割数量低于预期，因其在生成子集时缺乏足够敏感性。本文提出一种新方法：在推理阶段通过引入随机性的测试时搜索来增强已训练模型性能。首先，在图粗化过程中引入随机边选择，取代原有贪心策略；其次，提出基于粗化历史的分割算法（GraphCHiP），首次能够识别RCIs和框架容量不等式（FCIs）。在随机生成的CVRP实例上，实验表明该方法相比现有神经分离方法能更有效地降低对偶间隙。此外，本方法在特定实例上成功发现有效的FCIs，即便这类不等式极难识别。
原文摘要 · Abstract (English)
The identification of valid inequalities, such as the rounded capacity inequalities (RCIs), is a key component of cutting plane methods for the Capacitated Vehicle Routing Problem (CVRP). While a deep learning-based separation method can learn to find high-quality cuts, our analysis reveals that the model produces fewer cuts than expected because it is insufficiently sensitive to generate a diverse set of generated subsets. This paper proposes an alternative: enhancing the performance of a trained model at inference time through a new test-time search with stochasticity. First, we introduce stochastic edge selection into the graph coarsening procedure, replacing the previously proposed greedy approach. Second, we propose the Graph Coarsening History-based Partitioning (GraphCHiP) algorithm, which leverages coarsening history to identify not only RCIs but also, for the first time, the Framed capacity inequalities (FCIs). Experiments on randomly generated CVRP instances demonstrate the effectiveness of our approach in reducing the dual gap compared to the existing neural separation method. Additionally, our method discovers effective FCIs on a specific instance, despite the challenging nature of identifying such cuts.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。