  The cutting plane method is a key technique for successful branch-and-cut and
branch-price-and-cut algorithms that find the exact optimal solutions for
various vehicle routing problems (VRPs). Among various cuts, the rounded
capacity inequalities (RCIs) are the most fundamental. To generate RCIs, we
need to solve the separation problem, whose exact solution takes a long time to
obtain; therefore, heuristic methods are widely used. We design a
learning-based separation heuristic algorithm with graph coarsening that learns
the solutions of the exact separation problem with a graph neural network
(GNN), which is trained with small instances of 50 to 100 customers. We embed
our separation algorithm within the cutting plane method to find a lower bound
for the capacitated VRP (CVRP) with up to 1,000 customers. We compare the
performance of our approach with CVRPSEP, a popular separation software package
for various cuts used in solving VRPs. Our computational results show that our
approach finds better lower bounds than CVRPSEP for large-scale problems with
400 or more customers, while CVRPSEP shows strong competency for problems with
less than 400 customers.
