Invited Talk

December 15, 2015

"GPU accelerated algorithms for linear and quadratic assignment problem"

Speaker: Prof Rakesh Nagi

Professor, UIUC Donald Biggar Willett Professor, Dept. of Industrial & Enterprise Systems Engineering, UIUC, USA


Assignment Problems are fundamental to diverse branches of science and engineering. Some of their applications include information fusion, protein-protein interaction analysis, facility layout design, vehicle routing and resource scheduling. In this era of “big data” many of these applications demand solutions to very large instances of Assignment Problems in short amount of time. With a few exceptions, a vast majority of these Assignment Problems are NP-hard and many large instances are still not solved to provable optimality.

Our research proposes novel algorithms that harness the power of graphics cards present on desktop computers or large computational clusters to find exact solutions to massive and never-before-attempted instances of these fundamental Assignment Problems, and unlock new avenues for groundbreaking discoveries in various spheres of science and engineering.

In the first part, we describe a parallel version of the alternating tree Hungarian algorithm for solving the linear assignment problem (LAP). CUDA enabled NVIDIA graphics processing unit (GPU) is chosen as the parallel programming architecture because of its ability to perform intense computations on arrays and matrices. The main contribution of our research is an efficient parallelization of the augmenting path search phase of the Hungarian algorithm. Computational experiments on problems with up to 25 million variables reveal that our algorithm is on average 5-6 times faster than the sequential algorithm and the speedup increases with the problem size. A similar speedup is achieved for larger problems with up to 400 million variables, which are solved within 33 seconds on average. We also tested a multi-GPU version of the algorithm with up to 16 GPUs, which shows good scaling behavior for problems with up to 1.6 billion variables and dense cost matrix structure.

In the second part, we consider the Quadratic Assignment Problem (QAP), which is strongly NP-hard problem and it cannot be solved efficiently within a guaranteed time limit. Additionally, it is difficult to find a provable -optimal solution to QAP. The quadratic nature of the objective function also adds to the solution complexity. One of the ways of solving the QAP is to convert it into a Mixed Integer Linear Program (MILP) by introducing additional variables and constraints. Using the RLT2 linearization, we implement a dual ascent algorithm to find tight lower bounds and even solve many problems to optimality.

Keywords: Linear/Quadratic assignment problem; Parallel algorithm; Graphics processing unit; CUDA;


Rakesh Nagi is the Head and Donald Biggar Willett Professor of Industrial and Enterprise Systems Engineering Department at the University of Illinois, Urbana-Champaign. Previously he served as the Chair (2006-2012) and Professor of Industrial and Systems Engineering at the University at Buffalo (SUNY) (1993-2013). He received his Ph.D. (1991) and M.S. (1989) degrees in Mechanical Engineering from the University of Maryland at College Park, while he worked at the Institute for Systems Research and INRIA, France, and B.E. (1987) degree in Mechanical Engineering from University of Roorkee (now IIT-R),India.

He is a recipient of IIE Fellow Award (2010), UB’s “Sustained Achievement Award” in recognition of outstanding achievements in scholarly activity (2009), Business First of Buffalo’s “40 under Forty” award (2004), SME’s Milton C. Shaw Outstanding Young Manufacturing Engineer Award (1999), IIE’s Outstanding Young Industrial Engineer Award in Academia (1999), and National Science Foundation’s CAREER Award (1996). His papers have been published in journals including IIE Transactions, International Journal of Production Research, Journal of Manufacturing Systems, International Journal of Flexible Manufacturing Systems, Journal of Intelligent Manufacturing, Computers in Industry, Computer Integrated Manufacturing Systems, Management Science, Operations Research, Naval Research Logistics, European Journal of Operational Research, Annals of Operations Research, Computers and Operations Research, Computers and Industrial Engineering, and ASME and IEEE Transactions. His research interests are in Location theoretic approaches to Facilities Design, Agile Enterprises and Information-Based Manufacturing, Just-In-Time production of assemblies, Information Fusion, Intelligence Applications, Social Networks and Military Operations Research.

For More Information about Prof. Rakesh Nagi , Please Visit: Here