Explore a hybrid approach combining reinforcement learning and constraint programming for solving complex combinatorial optimization problems in this 28-minute lecture by Louis-Martin Rousseau from École Polytechnique de Montréal. Delve into the challenges of state-space explosion in combinatorial optimization and learn how deep reinforcement learning can be used to design effective heuristics for NP-hard problems. Discover a novel framework that bridges dynamic programming, constraint programming, and reinforcement learning to overcome limitations of current methods. Examine the application of this hybrid approach to two challenging problems: the traveling salesman problem with time windows and the 4-moments portfolio optimization problem. Gain insights into the performance advantages of this integrated solution compared to standalone reinforcement learning and constraint programming approaches, as well as its competitiveness with industrial solvers.
Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization
Institute for Pure & Applied Mathematics (IPAM) via YouTube
Overview
Syllabus
Intro
Search-based approaches
End-to-end learning-based approaches
Solving COPs by searching and learning Taking the best of the two worlds
Proposed approach
DP notation
From DP to CP
Proposed Framework
DL, RL and Search Architecture
Illustration on TSP
Link To RL environment
Constraint programming search
Adding Constraints
TSPTW: A DP model
TSPTW: Results
4- Moments Portfolio Optimization
PORT: Results
Conclusion and perspectives
Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization
Taught by
Institute for Pure & Applied Mathematics (IPAM)
Related Courses
-
Fundamentals of Reinforcement Learning
4.9 -
Decision Making and Reinforcement Learning
-
The Transformer Network for the Traveling Salesman Problem
-
Deep Learning for Combinatorial Optimization - Count Your Flops & Make Your Flops Count
-
Latent State Recovery in Reinforcement Learning - John Langford
-
Reinforcement Learning - Machine Learning Meets Control Theory
