{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/108143"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/108143","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"GPU-accelerated algorithms for the resource-constrained assignment problem","abstract":"The student, Olivia Reynen, accepted the attached license on 2020-05-01 at 19:39.","abstract_html":"The student, Olivia Reynen, accepted the attached license on 2020-05-01 at 19:39.","abstract_has_math":false,"creators":["Reynen, Olivia Helene"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Nagi, Rakesh"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-08-26T23:57:22Z","date_published":"2020-08-26T23:57:22Z","updated_at":"2026-07-22T22:24:47Z","subjects":["Resource-constrained assignment problem (RCAP)","Linear assignment problem (LAP)","Graphics processing unit (GPU)","Lagrangian relaxation","Branch-and-bound","Murty's algorithm"],"languages":["en"],"rights":["© 2020 Olivia Reynen"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/108143","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Nagi, Rakesh"]},{"key":"dc:creator","label":"Author","values":["Reynen, Olivia Helene"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-08-26T23:57:22Z","2022-08-26T23:58:55Z","2020-05-06","2020-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Resource-constrained assignment problem (RCAP)","Linear assignment problem (LAP)","Graphics processing unit (GPU)","Lagrangian relaxation","Branch-and-bound","Murty's algorithm"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["© 2020 Olivia Reynen"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/108143"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The student, Olivia Reynen, accepted the attached license on 2020-05-01 at 19:39.","The student, Olivia Reynen, submitted this Thesis for approval on 2020-05-01 at 20:31.","This Thesis was approved for publication on 2020-05-06 at 11:05.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15164 on 2020-08-25 at 17:28:37","Made available in DSpace on 2020-08-26T23:57:22Z (GMT). No. of bitstreams: 2 REYNEN-THESIS-2020.pdf: 259485 bytes, checksum: 0ebcb4af39236601839f7c06321dc06b (MD5) LICENSE.txt: 4210 bytes, checksum: 1dea1f31ffbf1318f51db50e3cad550f (MD5) Previous issue date: 2020-05-06","Embargo set by: Seth Robbins for item 115755 Lift date: 2022-08-26T23:57:28Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","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.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2022-05-01","Embargo set by: Seth Robbins for item 115755 Lift date: 2022-08-26T23:58:55Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["GPU-accelerated algorithms for the resource-constrained assignment problem"]}]}],"canonical_facts":{"dc:contributor":["Nagi, Rakesh"],"dc:creator":["Reynen, Olivia Helene"],"dc:date":["2020-08-26T23:57:22Z","2022-08-26T23:58:55Z","2020-05-06","2020-05"],"dc:description":["The student, Olivia Reynen, accepted the attached license on 2020-05-01 at 19:39.","The student, Olivia Reynen, submitted this Thesis for approval on 2020-05-01 at 20:31.","This Thesis was approved for publication on 2020-05-06 at 11:05.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15164 on 2020-08-25 at 17:28:37","Made available in DSpace on 2020-08-26T23:57:22Z (GMT). No. of bitstreams: 2 REYNEN-THESIS-2020.pdf: 259485 bytes, checksum: 0ebcb4af39236601839f7c06321dc06b (MD5) LICENSE.txt: 4210 bytes, checksum: 1dea1f31ffbf1318f51db50e3cad550f (MD5) Previous issue date: 2020-05-06","Embargo set by: Seth Robbins for item 115755 Lift date: 2022-08-26T23:57:28Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","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.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2022-05-01","Embargo set by: Seth Robbins for item 115755 Lift date: 2022-08-26T23:58:55Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/108143"],"dc:language":["en"],"dc:rights":["© 2020 Olivia Reynen"],"dc:subject":["Resource-constrained assignment problem (RCAP)","Linear assignment problem (LAP)","Graphics processing unit (GPU)","Lagrangian relaxation","Branch-and-bound","Murty's algorithm"],"dc:title":["GPU-accelerated algorithms for the resource-constrained assignment problem"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:47Z"}