Constrained Combinatorial Optimization with Reinforcement Learning

2020-06-22 · Ruben Solozabal, Josu Ceberio, Martin Takáč

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.

📄 PDF Abstract BibTeX arXiv:2006.11984

Code (0)

등록된 구현이 없습니다.

Tasks

Combinatorial OptimizationDeep Reinforcement Learningreinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Normalized Cut with Reinforcement Learning in Constrained Action Space

2025-05-20 · Qize Jiang, Linsey Pang, Alice Gatti, Mahima Aggarwal 외

Reinforcement Learning (RL) has emerged as an important paradigm to solve combinatorial optimization problems primarily due to its ability to learn heuristics that can generalize across problem instances. However, integr…

Combinatorial Optimization reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Latent Spherical Flow Policy for Reinforcement Learning with Combinatorial Actions

2026-01-29 · Lingkai Kong, Anagha Satish, Hezi Jiang, Akseli Kangaslahti 외 arxiv

Reinforcement learning (RL) with combinatorial action spaces remains challenging because feasible action sets are exponentially large and governed by complex feasibility constraints, making direct policy parameterization…

Reinforcement Learning

A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss Function for Combinatorial Optimization using Reinforcement Learning

2023-08-27 · Redwan Ahmed Rizvee, Md. Mosaddek Khan

Quadratic Unconstrained Binary Optimization (QUBO) is a generic technique to model various NP-hard combinatorial optimization problems in the form of binary variables. The Hamiltonian function is often used to formulate …

Combinatorial Optimization Graph Neural Network reinforcement-learning Reinforcement Learning

Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning

2019-11-12 · Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker 외

In this work, we introduce Graph Pointer Networks (GPNs) trained using reinforcement learning (RL) for tackling the traveling salesman problem (TSP). GPNs build upon Pointer Networks by introducing a graph embedding laye…

Combinatorial Optimization Graph Embedding Hierarchical Reinforcement Learning reinforcement-learning+3

Geometric Algorithms for Neural Combinatorial Optimization with Constraints

2025-10-28 · Nikolaos Karalias, Akbar Rafiey, Yifei Xu, Zhishang Luo 외 arxiv

Self-Supervised Learning (SSL) for Combinatorial Optimization (CO) is an emerging paradigm for solving combinatorial problems using neural networks. In this paper, we address a central challenge of SSL for CO: solving pr…

Self-Supervised Learning