Level 2 Reformulation Linearization Technique–Based Parallel Algorithms for Solving Large Quadratic Assignment Problems on Graphics Processing Unit Clusters

Ketan Date () and Rakesh Nagi ()
Additional contact information
Ketan Date: Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana–Champaign, Urbana, Illinois 61801
Rakesh Nagi: Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana–Champaign, Urbana, Illinois 61801

INFORMS Journal on Computing, 2019, vol. 31, issue 4, 771-789

Abstract: 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 multicore processors and compute unified device architecture–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 the level-2 reformulation linearization technique. The linear assignment subproblems in this procedure are solved using our accelerated Hungarian algorithm [Date K, Rakesh N (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 quadratic assignment problem library (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 a modest number of GPUs.

Keywords: quadratic assignment problem; linear assignment problem; branch-and-bound; parallel algorithm; graphics processing unit • CUDA • RLT2 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0866 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:4:p:771-789

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().