Parallel Algorithms for Solving Graph Assignment Problems

Rakesh Nagi, University of Illinois at Urbana-Champaign

Usage Details

The objective of this proposal is to 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 Multi-Dimensional Assignment Problem with Decomposable Costs (MDADC) and the Graph Matching (GM). Both problems are Mixed-Integer Linear Programs and they are strongly NP-hard. Typically, these problems are solved using tree search procedures, in which the lower bounds are calculated at each node by solving a Lagrangian dual problem. A search 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 tree search for solving MDADC to optimality; (2) To develop GPU-based implementation of the Truncated Search Tree heuristic to quickly obtain good feasible solutions to GM; and (3) 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 search trees 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.