# Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization

arXiv: https://arxiv.org/abs/2006.01610 · HTML: https://mlsanity.com/paper/2006.01610/

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2020.

## Built on by (most cited first, 30 of 63)

- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [Deep Policy Dynamic Programming for Vehicle Routing Problems](https://mlsanity.com/paper/2102.11756/) (2021)
- [BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization](https://mlsanity.com/paper/2301.03313/) (2023)
- [Pareto Set Learning for Neural Multi-objective Combinatorial Optimization](https://mlsanity.com/paper/2203.15386/) (2022)
- [The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights](https://mlsanity.com/paper/2203.02433/) (2022)
- [Challenges and Opportunities in Deep Reinforcement Learning with Graph Neural Networks: A Comprehensive review of Algorithms and Applications](https://mlsanity.com/paper/2206.07922/) (2022)
- [Learning to Handle Complex Constraints for Vehicle Routing Problems](https://mlsanity.com/paper/2410.21066/) (2024)
- [A Deep Reinforcement Learning Framework For Column Generation](https://mlsanity.com/paper/2206.02568/) (2022)
- [Pareto Set Learning for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2501.06773/) (2025)
- [Learning to Solve Vehicle Routing Problems: A Survey](https://mlsanity.com/paper/2205.02453/) (2022)
- [A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization](https://mlsanity.com/paper/2211.03074/) (2022)
- [BlendRL: A Framework for Merging Symbolic and Neural Policy Learning](https://mlsanity.com/paper/2410.11689/) (2024)
- [Solve routing problems with a residual edge-graph attention neural network](https://mlsanity.com/paper/2105.02730/) (2021)
- [Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning](https://mlsanity.com/paper/2506.02392/) (2025)
- [Learning Combinatorial Node Labeling Algorithms](https://mlsanity.com/paper/2106.03594/) (2021)
- [Deep Q-Learning based Reinforcement Learning Approach for Network Intrusion Detection](https://mlsanity.com/paper/2111.13978/) (2021)
- [Learning to Solve Multiple-TSP with Time Window and Rejections via Deep Reinforcement Learning](https://mlsanity.com/paper/2209.06094/) (2022)
- [Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling Salesman Problem](https://mlsanity.com/paper/2403.05318/) (2024)
- [Combining Constraint Programming Reasoning with Large Language Model Predictions](https://mlsanity.com/paper/2407.13490/) (2024)
- [Learning for routing: A guided review of recent developments and future directions](https://mlsanity.com/paper/2507.00218/) (2025)
- [SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning](https://mlsanity.com/paper/2102.09193/) (2021)
- [Fast Continuous and Integer L-shaped Heuristics Through Supervised Learning](https://mlsanity.com/paper/2205.00897/) (2022)
- [Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness](https://mlsanity.com/paper/2402.14847/) (2024)
- [Offline Reinforcement Learning for Learning to Dispatch for Job Shop Scheduling](https://mlsanity.com/paper/2409.10589/) (2024)
- [Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning](https://mlsanity.com/paper/2111.10810/) (2021)
- [Learning to Solve Soft-Constrained Vehicle Routing Problems with Lagrangian Relaxation](https://mlsanity.com/paper/2207.09860/) (2022)
- [Branch & Learn with Post-hoc Correction for Predict+Optimize with Unknown Parameters in Constraints](https://mlsanity.com/paper/2303.06698/) (2023)
- [Towards a Generic Representation of Combinatorial Problems for Learning-Based Approaches](https://mlsanity.com/paper/2403.06026/) (2024)
- [ENERO: Efficient Real-Time WAN Routing Optimization with Deep Reinforcement Learning](https://mlsanity.com/paper/2109.10883/) (2021)

## Abstract (arXiv)

Combinatorial optimization has found applications in numerous fields, from aerospace to transportation planning and economics. The goal is to find an optimal solution among a finite set of possibilities. The well-known challenge one faces with combinatorial optimization is the state-space explosion problem: the number of possibilities grows exponentially with the problem size, which makes solving intractable for large problems. In the last years, deep reinforcement learning (DRL) has shown its promise for designing good heuristics dedicated to solve NP-hard combinatorial optimization problems. However, current approaches have two shortcomings: (1) they mainly focus on the standard travelling salesman problem and they cannot be easily extended to other problems, and (2) they only provide an approximate solution with no systematic ways to improve it or to prove optimality. In another context, constraint programming (CP) is a generic tool to solve combinatorial optimization problems. Based on a complete search procedure, it will always find the optimal solution if we allow an execution time large enough. A critical design choice, that makes CP non-trivial to use in practice, is the branching decision, directing how the search space is explored. In this work, we propose a general and hybrid approach, based on DRL and CP, for solving combinatorial optimization problems. The core of our approach is based on a dynamic programming formulation, that acts as a bridge between both techniques. We experimentally show that our solver is efficient to solve two challenging problems: the traveling salesman problem with time windows, and the 4-moments portfolio optimization problem. Results obtained show that the framework introduced outperforms the stand-alone RL and CP solutions, while being competitive with industrial solvers.