Reinforcement Learning for Combinatorial Optimization: A Survey

DOI10.1016/J.COR.2021.105400MaRDI QIDQ6336314arXivFDO

Authors Nina Mazyavkina, Sergey A. Sviridov, S. V. Ivanov, Evgeny Burnaev

Publication date 7 March 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.COR.2021.105400

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

arXiv classification

cs.LGmath.COmath.OCstat.ML

Abstract: 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.

This page was built for publication: Reinforcement Learning for Combinatorial Optimization: A Survey

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6336314)