Reinforcement learning for combinatorial optimization: A survey

• Published in: Computers & operations research 2021-10, Vol.134, p.105400, Article 105400
• Main Authors: Mazyavkina, Nina, Sviridov, Sergey, Ivanov, Sergei, Burnaev, Evgeny
• Format: Article
• Language: English
• Subjects: Algorithms; Combinatorial analysis; Combinatorial optimization; Heuristic; Machine learning; Operations research; Optimization; Policy-based methods; Reinforcement learning; Value-based methods
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2021.105400

Many traditional algorithms for solving combinatorial optimization problems involve using hand-crafted heuristics that sequentially construct a solution. Such heuristics are designed by domain experts and may often be suboptimal due to the hard nature of the problems. Reinforcement learning (RL) proposes a good alternative to automate the search of these heuristics by training an agent in a supervised or self-supervised manner. In this survey, we explore the recent advancements of applying RL frameworks to hard combinatorial problems. Our survey provides the necessary background for operations research and machine learning communities and showcases the works that are moving the field forward. We juxtapose recently proposed RL methods, laying out the timeline of the improvements for each problem, as well as we make a comparison with traditional algorithms, indicating that RL models can become a promising direction for solving combinatorial problems. •Survey explores synergy of combinatorial optimization and reinforcement learning.•It covers recent papers showing how RL can be applied to solve canonical CO problems.•Graph neural networks are used as a method for graph representation in RL for CO.•Policy-based and value-based RL methods are used to learn the solutions to CO tasks.•Most of the reported experiments do not overlap.•This makes it hard to fairly compare the surveyed methods.