Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization

Overview

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.

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