Solving the Quadratic Assignment Problem using Deep Reinforcement
  Learning
Puneet S. Bagga Arthur Delarue
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.