Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective

2024-04-09 · Victor-Alexandru Darvariu, Stephen Hailes, Mirco Musolesi

Graphs are a natural representation for systems based on relations between connected entities. Combinatorial optimization problems, which arise when considering an objective function related to a process of interest on discrete structures, are often challenging due to the rapid growth of the solution space. The trial-and-error paradigm of Reinforcement Learning has recently emerged as a promising alternative to traditional methods, such as exact algorithms and (meta)heuristics, for discovering better decision-making strategies in a variety of disciplines including chemistry, computer science, and statistics. Despite the fact that they arose in markedly different fields, these techniques share significant commonalities. Therefore, we set out to synthesize this work in a unifying perspective that we term Graph Reinforcement Learning, interpreting it as a constructive decision-making method for graph problems. After covering the relevant technical background, we review works along the dividing line of whether the goal is to optimize graph structure given a process of interest, or to optimize the outcome of the process itself under fixed graph structure. Finally, we discuss the common challenges facing the field and open research questions. In contrast with other surveys, the present work focuses on non-canonical graph problems for which performant algorithms are typically not known and Reinforcement Learning is able to provide efficient and effective solutions.

📄 PDF Abstract BibTeX arXiv:2404.06492

Code (0)

등록된 구현이 없습니다.

Tasks

Combinatorial OptimizationDecision Making reinforcement-learning Reinforcement Learning

Methods 이 논문이 사용한 방법론

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

Combinatorial Optimization Augmented Machine Learning

2026-01-15 · Maximilian Schiffer, Heiko Hoppe, Yue Su, Louis Bouvier 외 arxiv

Combinatorial optimization augmented machine learning (COAML) has recently emerged as a powerful paradigm for integrating predictive models with combinatorial decision-making. By embedding combinatorial optimization orac…

Stochastic Optimization Reinforcement Learning

A Unifying Survey of Reinforced, Sensitive and Stigmergic Agent-Based Approaches for E-GTSP

2012-08-24 · Camelia-M. Pintea

The Generalized Traveling Salesman Problem (GTSP) is one of the NP-hard combinatorial optimization problems. A variant of GTSP is E-GTSP where E, meaning equality, has the constraint: exactly one node from a cluster of a…

Combinatorial Optimization Traveling Salesman Problem

Reinforcement Learning for Combinatorial Optimization: A Survey

2020-03-07 · Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, Evgeny Burnaev

Many traditional algorithms for solving combinatorial optimization problems involve using hand-crafted heuristics that sequentially construct a solution. Such heuristics are designed by domain experts and may often be su…

Combinatorial Optimization Decision Making reinforcement-learning Reinforcement Learning+2

Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking

2020-05-22 · Natalia Vesselinova, Rebecca Steinert, Daniel F. Perez-Ramirez, Magnus Boman

Existing approaches to solving combinatorial optimization problems on graphs suffer from the need to engineer each problem algorithmically, with practical problems recurring in many instances. The practical side of theor…

BIG-bench Machine Learning Combinatorial Optimization

A Survey on Reinforcement Learning for Combinatorial Optimization

2020-08-17 · Yunhao Yang, Andrew Whinston

This paper gives a detailed review of reinforcement learning (RL) in combinatorial optimization, introduces the history of combinatorial optimization starting in the 1950s, and compares it with the RL algorithms of recen…

Combinatorial Optimization Deep Learning reinforcement-learning Reinforcement Learning+3