  This paper discusses efficient parallel algorithms for obtaining strong lower
bounds and exact solutions for large instances of the Quadratic Assignment
Problem (QAP). Our parallel architecture is comprised of both multi-core
processors and Compute Unified Device Architecture (CUDA) enabled NVIDIA
Graphics Processing Units (GPUs) on the Blue Waters Supercomputing Facility at
the University of Illinois at Urbana-Champaign. We propose novel
parallelization of the Lagrangian Dual Ascent algorithm on the GPUs, which is
used for solving a QAP formulation based on Level-2 Refactorization
Linearization Technique (RLT2). The Linear Assignment sub-problems (LAPs) in
this procedure are solved using our accelerated Hungarian algorithm [Date,
Ketan, Rakesh Nagi. 2016. GPU-accelerated Hungarian algorithms for the Linear
Assignment Problem. Parallel Computing 57 52-72]. We embed this accelerated
dual ascent algorithm in a parallel branch-and-bound scheme and conduct
extensive computational experiments on single and multiple GPUs, using problem
instances with up to 42 facilities from the QAPLIB. The experiments suggest
that our GPU-based approach is scalable and it can be used to obtain tight
lower bounds on large QAP instances. Our accelerated branch-and-bound scheme is
able to comfortably solve Nugent and Taillard instances (up to 30 facilities)
from the QAPLIB, using modest number of GPUs.
