A Neural Separation Algorithm for the Rounded Capacity Inequalities

Hyeonah Kim (), Jinkyoo Park () and Changhyun Kwon ()
Additional contact information
Hyeonah Kim: Department of Industrial and Systems Engineering, KAIST, Daejeon 34141, Republic of Korea
Jinkyoo Park: Department of Industrial and Systems Engineering, KAIST, Daejeon 34141, Republic of Korea; OMELET, Daejeon 34051, Republic of Korea
Changhyun Kwon: Department of Industrial and Systems Engineering, KAIST, Daejeon 34141, Republic of Korea; OMELET, Daejeon 34051, Republic of Korea

INFORMS Journal on Computing, 2024, vol. 36, issue 4, 987-1005

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, whereas CVRPSEP shows strong competency for problems with less than 400 customers.

Keywords: vehicle routing; integer programming; cutting plane; artificial intelligence (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0310 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:4:p:987-1005

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().