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

Multidimensional assignment problem (MAP) is one of the many formulations of data association problem which categorizes data based on various data sources. A higher number of data sources ensures an accurate categorization of data. But it also leads to a significant increase in the amount of data, consequently increasing the computation time where quick results are sought. In this work, we used Lagrangian relaxation technique to solve the MAPs with decomposable costs. But the major contribution was an efficient parallelization of this algorithm on a graphics processing unit (GPU) based programming architecture. Bigger problems with larger data sets were solved by using multiple processors with each having a GPU of its own. This not only handled the data by distributing it among the processors, but also increased the amount of parallelization to give us good iteration times. Problems with 796 million cost variables were solved on varying number of processors between 1 and 64, with significantly fast iteration times. Owing to the good scalability of the developed parallel solver, we successfully solved problems with 31 billion cost variables on processors ranging from 64 to 128 in good amount of time.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2018

Author dc:creator

• Natu, Shardul

Contributors dc:contributor

• Nagi, Rakesh

• Multidimensional assignment problem (MAP)
• Linear assignment problem (LAP)
• Graphics processing unit (GPU)
• Lagrangian relaxation.

Statement dc:rights

• Copyright 2018 Shardul Natu

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/101117

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/101117