Abstract: Combinatorial optimization (CO) has a wide range of applications in various fields such as economics, management science, biology, and earth science. Traditionally, these NP-hard problems are solved both with accurate algorithms like Branch-and-Bound (B&B) and dynamic programming (DP), and approximate algorithms like relaxation, locally searching and heuristic searching. The demand for new learning-based methods for combinatorial optimization problems keeps growing with the increasement in problem size and efficiency requirements in practical applications. In recent years, new ideas using deep reinforcement learning (DRL) techniques achieve much progress on combinatorial optimization problems with medium and large scales, which have not only faster running speed than traditional methods but also stronger model representation power than supervised learning methods.
In this lecture, we present a review of several kinds of deep reinforcement learning methods in combinatorial optimization, including end-to-end policy gradient approaches, Q-learning with graph neural networks, and heuristic improvement with DRL. We will introduce many important works in DRL for CO such as Ptr-Network (Vinyals et al., 2015), Structure-to-vector Network (Dai et al., 2017), NeuRewriter (Chen et al., 2019), and so on.
