PARALLEL ALGORITHMS FOR SOLVING LARGE ASSIGNMENT PROBLEMS

Rakesh Nagi, University of Illinois at Urbana-Champaign

Usage Details

The objective of this proposal is to extend the current allocation or obtain a new allocation on the Blue Waters for development and testing of fast and scalable GPU-based parallel algorithms, which can solve large instances of the Quadratic Assignment Problem (QAP) and the Multi-Dimensional Assignment Problem with Decomposable Costs (MDADC). Both problems are Mixed-Integer Linear Programs (MILP) and they are strongly NP-hard. Typically, these problems are solved using branch-and-bound, in which the lower bounds are calculated at each node by solving a Lagrangian dual problem. A branch-and-bound tree contains exponential number of nodes, each of which corresponds to one subproblem. These subproblems need to be solved efficiently to keep the execution times in check. Therefore, the goals of our research are: (1) To develop and test parallel branch-and-bound scheme for solving QAP and MDADC to optimality; and (2) To develop GPU-based efficient algorithms for solving the Lagrangian dual subproblems at each node, for obtaining strong lower bounds. For this project, the computational resources from the Blue Waters will be extremely beneficial, since parallel exploration of the branch-and-bound tree will most definitely require large number of processing elements. Also, the availability of a host of GPU-enabled processors will significantly speed up the lower bound calculation at each node, allowing us to solve large problems that remain unsolved to this date. It is important to note that for the QAP, "large size" means problems with 30 ≤ n ≤ 40 facilities, because QAP is known to be computationally intensive.