Kevin Tierney - Search heuristics for solving combinatorial optimization problems with deep RL

Part of Discrete Optimization Talks: talks.discrete...
Kevin Tierney - Universität Bielefeld
Search heuristics for solving combinatorial optimization problems with deep reinforcement learning
Speaker webpage: www.uni-bielef...
Abstract: Methods using deep reinforcement learning to learn how to solve combinatorial optimization (CO) problems are rapidly approaching the performance of traditional OR heuristics. The performance gains of these methods can be contributed to two factors, namely the quality of the deep learned models and the effectiveness of using these models within a search process. I present my lab's work with Samsung SDS on the latter challenge, for which we have developed problem-independent search methods that can be integrated with deep learned models to find high-quality solutions to difficult CO problems. First, I will discuss efficient active search, which harnesses backpropagation during search to adjust a previously learned model to the problem instance being solved. Second, I will describe simulation-guided beam search, which combines EAS with a GPU-based beam search and solution rollouts to further guide the search process. Both search methods are compared to machine learning-based and traditional OR methods on routing and scheduling problems, showing that they come close, and in some cases beat, the traditional approaches.
Bio: Kevin Tierney is a full professor for Decision and Operation Technologies at Bielefeld University in Germany. He holds a B.Sc. in Computer Science from Rochester Institute of Technology, an Sc.M. in Computer Science from Brown University, and a PhD from the IT University of Copenhagen in Denmark. He was previously an assistance professor at Paderborn University. His research interests include algorithm configuration, learning to solve optimization problems, and solving logistics problems. His work on Neural Large Neighborhood Search won the distinguished paper award at ECAI 2020.

[@zohrenoor4176]

Very helpful. Thank you, Kevin.

[@nathansudermann-merx4586]

Very interesting, thank you, Kevin!