GPU-accelerated Lagrangian heuristic for multidimensional assignment problems with decomposable costs

Shardul Natu, Ketan Date, Rakesh Nagi

Research output: Contribution to journalArticlepeer-review


In this paper, we describe a GPU-accelerated parallel algorithm for the axial Multidimensional Assignment Problem with Decomposable Costs (MDADC), which is one of the most fundamental formulations for data association. MDADC is known to be NP-hard and is large-dimensioned in most realistic cases; hence, heuristic solutions with qualified optimality gaps is the best one can hope for, given the state-of-knowledge. The main contribution of this paper is an efficient parallelization of the Lagrangian subgradient search algorithm specifically targeted towards the Graphics Processing Units (GPUs) based on the NVIDIA Compute Unified Device Architecture (CUDA). A GPU-accelerated Linear Assignment Problem (LAP) solver is leveraged in concert with the Lagrangian scheme for further speed-up. We also implemented a multi-GPU variant of this algorithm which maintains a good speedup profile, when tested on problems with 31 billion variables, on up to 128 GPUs.

Original languageEnglish (US)
Article number102666
JournalParallel Computing
StatePublished - Sep 2020


  • CUDA
  • Graphics processing unit
  • Lagrangian heuristic
  • Multi-dimensional assignment problem
  • Parallel algorithm

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'GPU-accelerated Lagrangian heuristic for multidimensional assignment problems with decomposable costs'. Together they form a unique fingerprint.

Cite this