Files in this item

FilesDescriptionFormat

application/pdf

application/pdfREYNEN-THESIS-2020.pdf (259kB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:GPU-accelerated algorithms for the resource-constrained assignment problem
Author(s):Reynen, Olivia Helene
Advisor(s):Nagi, Rakesh
Department / Program:Industrial&Enterprise Sys Eng
Discipline:Industrial Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(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.
Issue Date:2020-05-06
Type:Thesis
URI:http://hdl.handle.net/2142/108143
Rights Information:© 2020 Olivia Reynen
Date Available in IDEALS:2020-08-26
Date Deposited:2020-05


This item appears in the following Collection(s)

Item Statistics