GPU-Based Parallel Computing Methods for Solving Large Scale Assignment Problems

Rakesh Nagi, University of Illinois at Urbana-Champaign

Usage Details

The goal of this project is to develop and test fast and scalable GPU-enabled methods for obtaining tight lower bounds on large instances of the quadratic assignment problem (QAP). The QAP is linearized using an enhanced model, which can be naturally decomposed into multiple linear assignment problems (LAP), after dualizing the complicating constraints with the help of Lagrangian relaxation. The Lagrangian dual problem will be solved using a GPU-based parallel sub-gradient optimization method, whereas the linear assignment sub-problems will be solved using a GPU-based parallel Hungarian algorithm. The primary objective is to test the scalability of these algorithms on medium-sized problems, in preparation for deploying them on larger cluster to obtain lower bounds on large sized QAPs, which remain unsolved to this date. The secondary objective is to use these lower bounds and optimally solve these large problems, using parallel branch and bound method.