# Reinforcement learning based local search for grouping problems: A case study on graph coloring

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Apr 2016.

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

- [Rethinking Graph Neural Networks for the Graph Coloring Problem](https://mlsanity.com/paper/2208.06975/) (2022)
- [SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning](https://mlsanity.com/paper/2102.09193/) (2021)
- [A deep learning guided memetic framework for graph coloring problems](https://mlsanity.com/paper/2109.05948/) (2021)
- [Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks](https://mlsanity.com/paper/2304.04051/) (2023)
- [A Survey on Machine Learning Solutions for Graph Pattern Extraction](https://mlsanity.com/paper/2204.01057/) (2022)
- [Combining Monte Carlo Tree Search and Heuristic Search for Weighted Vertex Coloring](https://mlsanity.com/paper/2304.12146/) (2023)

## Abstract (arXiv)

Grouping problems aim to partition a set of items into multiple mutually disjoint subsets according to some specific criterion and constraints. Grouping problems cover a large class of important combinatorial optimization problems that are generally computationally difficult. In this paper, we propose a general solution approach for grouping problems, i.e., reinforcement learning based local search (RLS), which combines reinforcement learning techniques with descent-based local search. The viability of the proposed approach is verified on a well-known representative grouping problem (graph coloring) where a very simple descent-based coloring algorithm is applied. Experimental studies on popular DIMACS and COLOR02 benchmark graphs indicate that RLS achieves competitive performances compared to a number of well-known coloring algorithms.