# Constrained Combinatorial Optimization with Reinforcement Learning

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

## Key facts

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

## Built on by (most cited first, 8 of 8)

- [Learning to generalize Dispatching rules on the Job Shop Scheduling](https://mlsanity.com/paper/2206.04423/) (2022)
- [Assessment of Reinforcement Learning Algorithms for Nuclear Power Plant Fuel Optimization](https://mlsanity.com/paper/2305.05812/) (2023)
- [Multi-Objective Reinforcement Learning-based Approach for Pressurized Water Reactor Optimization](https://mlsanity.com/paper/2312.10194/) (2023)
- [Lattice Protein Folding with Variational Annealing](https://mlsanity.com/paper/2502.20632/) (2025)
- [Risk-Aware Continuous Control with Neural Contextual Bandits](https://mlsanity.com/paper/2312.09961/) (2023)
- [RELS-DQN: A Robust and Efficient Local Search Framework for Combinatorial Optimization](https://mlsanity.com/paper/2304.06048/) (2023)
- [Capacity-Aware Planning and Scheduling in Budget-Constrained Multi-Agent MDPs: A Meta-RL Approach](https://mlsanity.com/paper/2410.21249/) (2024)
- [Learn to Solve Vehicle Routing Problems ASAP: A Neural Optimization Approach for Time-Constrained Vehicle Routing Problems with Finite Vehicle Fleet](https://mlsanity.com/paper/2411.04777/) (2024)

## Abstract (arXiv)

This paper presents a framework to tackle constrained combinatorial optimization problems using deep Reinforcement Learning (RL). To this end, we extend the Neural Combinatorial Optimization (NCO) theory in order to deal with constraints in its formulation. Notably, we propose defining constrained combinatorial problems as fully observable Constrained Markov Decision Processes (CMDP). In that context, the solution is iteratively constructed based on interactions with the environment. The model, in addition to the reward signal, relies on penalty signals generated from constraint dissatisfaction to infer a policy that acts as a heuristic algorithm. Moreover, having access to the complete state representation during the optimization process allows us to rely on memory-less architectures, enhancing the results obtained in previous sequence-to-sequence approaches. Conducted experiments on the constrained Job Shop and Resource Allocation problems prove the superiority of the proposal for computing rapid solutions when compared to classical heuristic, metaheuristic, and Constraint Programming (CP) solvers.