English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper discusses efficient parallel algorithms for obtaining strong lowerbounds and exact solutions for large instances of the Quadratic AssignmentProblem (QAP). Our parallel architecture is comprised of both multi-coreprocessors and Compute Unified Device Architecture (CUDA) enabled NVIDIAGraphics Processing Units (GPUs) on the Blue Waters Supercomputing Facility atthe University of Illinois at Urbana-Champaign. We propose novelparallelization of the Lagrangian Dual Ascent algorithm on the GPUs, which isused for solving a QAP formulation based on Level-2 RefactorizationLinearization Technique (RLT2). The Linear Assignment sub-problems (LAPs) inthis procedure are solved using our accelerated Hungarian algorithm [Date,Ketan, Rakesh Nagi. 2016. GPU-accelerated Hungarian algorithms for the LinearAssignment Problem. Parallel Computing 57 52-72]. We embed this accelerateddual ascent algorithm in a parallel branch-and-bound scheme and conductextensive computational experiments on single and multiple GPUs, using probleminstances with up to 42 facilities from the QAPLIB. The experiments suggestthat our GPU-based approach is scalable and it can be used to obtain tightlower bounds on large QAP instances. Our accelerated branch-and-bound scheme isable to comfortably solve Nugent and Taillard instances (up to 30 facilities)from the QAPLIB, using modest number of GPUs.

RLT2-based Parallel Algorithms for Solving Large Quadratic Assignment Problems on Graphics Processing Unit Clusters