YoVDO

Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization

Offered By: Institute for Pure & Applied Mathematics (IPAM) via YouTube

Tags

Reinforcement Learning Courses Artificial Intelligence Courses Algorithm Design Courses Dynamic programming Courses Constraint Programming Courses Combinatorial Optimization Courses Traveling Salesman Problem Courses

Course Description

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


Taught by

Institute for Pure & Applied Mathematics (IPAM)

Related Courses

Introduction to Artificial Intelligence
Stanford University via Udacity
Probabilistic Graphical Models 1: Representation
Stanford University via Coursera
Artificial Intelligence for Robotics
Stanford University via Udacity
Computer Vision: The Fundamentals
University of California, Berkeley via Coursera
Learning from Data (Introductory Machine Learning course)
California Institute of Technology via Independent