Graph Q-Learning for Combinatorial Optimization
This work addresses combinatorial optimization, a challenging domain in computer science, by introducing a machine learning-based approach that is more efficient than traditional methods.
The paper tackles combinatorial optimization problems by formulating them as sequential decision-making tasks and using graph neural networks trained with Q-learning to learn policies that build candidate solutions, achieving performance close to state-of-the-art heuristic solvers with fewer parameters and less training time.
Graph-structured data is ubiquitous throughout natural and social sciences, and Graph Neural Networks (GNNs) have recently been shown to be effective at solving prediction and inference problems on graph data. In this paper, we propose and demonstrate that GNNs can be applied to solve Combinatorial Optimization (CO) problems. CO concerns optimizing a function over a discrete solution space that is often intractably large. To learn to solve CO problems, we formulate the optimization process as a sequential decision making problem, where the return is related to how close the candidate solution is to optimality. We use a GNN to learn a policy to iteratively build increasingly promising candidate solutions. We present preliminary evidence that GNNs trained through Q-Learning can solve CO problems with performance approaching state-of-the-art heuristic-based solvers, using only a fraction of the parameters and training time.