A Neural Separation Algorithm for the Rounded Capacity Inequalities

arXiv2306.17283MaRDI QIDQ6442040

Author name not available (Why is that?)

Publication date: 29 June 2023

Abstract: 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.

Has companion code repository: https://github.com/hyeonahkimm/neuralsep

This page was built for publication: A Neural Separation Algorithm for the Rounded Capacity Inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6442040)