GPU-accelerated algorithms for the resource-constrained assignment problem

The Resource-Constrained Assignment Problem (RCAP) aims to find the minimum cost one-to-one matching between two sets of N nodes while meeting one or more resource constraints. Its applications include machine scheduling, job assignment, facility layout, and others. This problem is known to be NP-hard. A Lagrangian relaxation of the side constraints transforms the problem structure into a Linear Assignment Problem (LAP), which is known to be polynomially solvable. This thesis presents two solution methods for the RCAP that utilize this Lagrangian relaxation with an LAP structure and leverage GPU parallel computing. The first solution method involves performing a multiplier update procedure to obtain a good lower bound to start with and then using a GPU-accelerated version of Murty's algorithm to iterate through solutions in ascending order until the optimality gap is closed. The second solution method is a GPU-accelerated branch-and-bound algorithm that uses a best-first search method and polytomic branching with the same multiplier update procedure being performed every time a new node is explored. Computational testing was conducted on several test problems of two different types, randomly generated costs and weights and negatively correlated costs and weights. The results show that the GPU-accelerated Murty's algorithm performs better for the singly-constrained randomly generated problems, while the branch-and-bound algorithm performs better for all other problems tested.U of I OnlyAuthor requested U of Illinois access only (OA after 2yrs) in Vireo ETD syste