GPU-accelerated algorithms for the resource-constrained assignment problem

Reynen, Olivia Helene

Permalink

https://hdl.handle.net/2142/108143 Copy

Description

Title

GPU-accelerated algorithms for the resource-constrained assignment problem

Author(s)

Reynen, Olivia Helene

Issue Date

2020-05-06

Director of Research (if dissertation) or Advisor (if thesis)

Nagi, Rakesh

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Resource-constrained assignment problem (RCAP)
• Linear assignment problem (LAP)
• Graphics processing unit (GPU)
• Lagrangian relaxation
• Branch-and-bound
• Murty's algorithm

Abstract

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.

Graduation Semester

2020-05

Type of Resource

Thesis

Permalink

http://hdl.handle.net/2142/108143

Copyright and License Information

© 2020 Olivia Reynen

Owning Collections