Parallel Algorithms for Solving Large Assignment Problems -- Ketan Date

In this work, we discuss efficient parallel algorithms for optimally solving large instances of the Linear Assignment Problem (LAP) and 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 supercomputer at the University of Illinois at Urbana-Champaign. We propose novel parallelization of the Hungarian algorithm on the GPUs, which shows excellent parallel speedup for large LAPs, with up to 400 million variables. We also propose novel parallelization of the Dual Ascent algorithm on the GPUs, for solving the RLT2 linearization of the QAP, with the LAP sub-problems being solved using our parallel Hungarian algorithm. We show that this GPU-accelerated approach can be used to obtain quick and tight lower bounds on large instances of the QAP (with up to 42 facilities and locations), which can be extremely valuable in a branch-and-bound scheme.