Deep learning for combinatorial optimization problems

Abstract

Combinatorial Optimization Problems (COPs) are a family of problems that search over a finite set of solutions to find the best one with the objective function optimized. COPs have extensive real-world applications in various industries, such as vehicle navigation systems, logistics and supply chain management. And a better solution for the problem could lead to a significantly large amount of cost reduction. Unfortunately, many important COPs including Vehicle Routing Problems, Boolean Satisfiability Problems and Scheduling Problems are extremely hard to solve, where the exact methods to find the best solutions have the worst-case exponential time complexity in general, therefore, usually too time-consuming to apply for problems with medium to large sizes. In contrast, though lacking theoretical guarantees, heuristic methods can find good solutions in a relatively short time and are usually more preferred for industrial applications. Traditional heuristic methods search over the solution space based on the hand-crafted rules designed manually by researchers, which require extensive expert knowledge for specific problems. On the contrary, recent studies have been focusing on training deep learning models to learn the heuristics from data samples. With the great learning ability of deep neural networks, potentially better heuristics could be extracted without the heavy research time, especially for the less well-studied problems with complicated constraints and objective functions. The deep learning models can either be trained by supervised learning to imitate the solutions obtained from highly optimized traditional algorithms or by reinforcement learning to explore the environment of solution space and optimize the objective values. In this report, we mainly focus on one of the most important families of COPs, the Vehicle Routing Problem (VRP). However, most ideas behind the proposed models could also be applied to other COPs in general. Though we tackle various aspects with different model architectures and training algorithms, the goal is to find better solutions in a shorter time.