Solving the QAP by Two-Stage Graph Pointer Networks and Reinforcement Learning

2024/03/31 by Satoko Iida, Iida, Satoko, Ryota Yasudo +1
Engineering · #FOS: Computer and information sciences #Fault Detection and Control Systems #Image Processing Techniques and Applications #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2404.00539

openalex publication_date 2024/03/31 · openalex created_date 2024/04/04 · openalex updated_date 2026/07/28

Abstract

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.

Related

• Solving the Quadratic Assignment Problem using Deep Reinforcement Learning
• On the Difficulty of Generalizing Reinforcement Learning Framework for Combinatorial Optimization
• Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
• Pointer Networks with Q-Learning for Combinatorial Optimization
• Multi-objective Pointer Network for Combinatorial Optimization