Learning-Based Separation Algorithms for Vehicle Routing Problems

Abstract

For solving vehicle routing problems, an important class of combinatorial optimization problems, cutting planes play a crucial role in tightening the dual bounds; they are a basis for many successful large-scale algorithms such as branch-price-and-cut algorithms. Given an LP solution, identifying a hyperplane that separates it from the original feasible set is called the separation problem. Unfortunately, most separation problems themselves are NP-hard combinatorial optimization problems. In practice, heuristic algorithms have been used to find various types of cutting planes, such as rounded capacity inequalities, framed capacity inequalities, and strengthened comb inequalities. We propose learning-based approaches to solving separation problems by training neural networks using supervised and reinforcement learning. This talk will demonstrate the potential of learning-based methods and also discuss their limitations.