cs.AIOct 1, 2025

Test-Time Search in Neural Graph Coarsening Procedures for the Capacitated Vehicle Routing Problem

Authors: Yoonju Sim, Hyeonah Kim, Changhyun Kwon

Organizations: Department of Industrial and Systems Engineering, KAIST, Daejeon, 34141, Republic of Korea · Mila, Universit´e de Montr´eal, Canada · Omelet, Inc., Daejeon, 34051, Republic of Korea

Abstract

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.

Figures & tables

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. SAG-Sep: Sparse Augmented Graphs and Onion-Guided Search for Rounded Capacity Cut Separation

    Oct 27, 2026Haoran Liu, Guanyi Wang, Yu YangVehicle RoutingNeural Combinatorial Optimization

  2. RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem

    Oct 10, 2026Vladimir Kirill Bickov, Neil Yorke-SmithNeural Combinatorial OptimizationVehicle Routing

  3. GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer

    Sep 4, 2026Youssef Kamel Rezk, Paweł GoraQuantum AnnealingGraph Coarsening