Solving the Quadratic Assignment Problem using Deep Reinforcement Learning

Puneet S. Bagga, Arthur Delarue
10/2/2023
cs.LGcs.AImath.OC

No official code found. Best implementation: ebrahimpichka/QAP-RL (6 stars, last commit 2023-12-29).

Abstract

The Quadratic Assignment Problem (QAP) is an NP-hard problem which has proven particularly challenging to solve: unlike other combinatorial problems like the traveling salesman problem (TSP), which can be solved to optimality for instances with hundreds or even thousands of locations using advanced integer programming techniques, no methods are known to exactly solve QAP instances of size greater than 30. Solving the QAP is nevertheless important because of its many critical applications, such as electronic wiring design and facility layout selection. We propose a method to solve the original Koopmans-Beckman formulation of the QAP using deep reinforcement learning. Our approach relies on a novel double pointer network, which alternates between selecting a location in which to place the next facility and a facility to place in the previous location. We train our model using A2C on a large dataset of synthetic instances, producing solutions with no instance-specific retraining necessary. Out of sample, our solutions are on average within 7.5% of a high-quality local search baseline, and even outperform it on 1.2% of instances.

View on arXivView PDF

Code Implementations(1)

ebrahimpichka/QAP-RLCommunity65%

Unofficial implemnetation of "Solving Quadratic Assignemt Problem using Deep Reinforcement Learning" (https://arxiv.org/abs/2310.01604)

60Python, Jupyter NotebookNov 14, 20232 years ago
combinatorial-optimizationdeep-reinforcement-learningml4coneural-combinatorial-optimizationoperations-research+3 more

Similar Papers

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

91% match2024

Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem

87% match2 repos172024

Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems

80% match1 repo322024

Unsupervised Learning for Quadratic Assignment

80% match1 repo2025

Deep Distributed Optimization for Large-Scale Quadratic Programming

79% match2024

Large-scale Urban Facility Location Selection with Knowledge-informed Reinforcement Learning

78% match2024

Cite this paper

@article{bagga2023solving,
  title  = {Solving the Quadratic Assignment Problem using Deep Reinforcement Learning},
  author = {Puneet S. Bagga and Arthur Delarue},
  year   = {2023},
  eprint = {2310.01604},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2310.01604v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2310.01604.svg)](https://codeofpaper.com/paper/2310.01604)

Discussion