Solving the QAP by Two-Stage Graph Pointer Networks and Reinforcement Learning
On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization
Abstract (arXiv)
Quadratic Assignment Problem (QAP) is a practical combinatorial optimization problems that has been studied for several years. Since it is NP-hard, solving large problem instances of QAP is challenging. Although heuristics can find semi-optimal solutions, the execution time significantly increases as the problem size increases. Recently, solving combinatorial optimization problems by deep learning has been attracting attention as a faster solver than heuristics. Even with deep learning, however, solving large QAP is still challenging. In this paper, we propose the deep reinforcement learning model called the two-stage graph pointer network (GPN) for solving QAP. Two-stage GPN relies on GPN, which has been proposed for Euclidean Traveling Salesman Problem (TSP). First, we extend GPN for general TSP, and then we add new algorithms to that model for solving QAP. Our experimental results show that our two-stage GPN provides semi-optimal solutions for benchmark problem instances from TSPlib and QAPLIB.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 2 of its 16 references that are in the map. First posted on arXiv 31 Mar 2024.
Builds on
2 of 16 references.
References · 2
- 2015Pointer Networkscited by 895
- 2019Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learningcited by 78
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2024Graph Q-Learning for Combinatorial Optimization
- 2025A Distributed Training Architecture For Combinatorial Optimization
- 2025Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
- 2025A Unified Deep Reinforcement Learning Approach for Close Enough Traveling Salesman Problem
- 2026Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimization
- 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective
- 2025Reinforcement Learning for Game-Theoretic Resource Allocation on Graphs
- 2025Vehicle Routing Problems via Quantum Graph Attention Network Deep Reinforcement Learning