{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/101117"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/101117","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"GPU-based Lagrangian heuristic for multidimensional assignment problems with decomposable costs","abstract":"Multidimensional assignment problem (MAP) is one of the many formulations of data association problem which categorizes data based on various data sources. A higher number of data sources ensures an accurate categorization of data. But it also leads to a significant increase in the amount of data, consequently increasing the computation time where quick results are sought. In this work, we used Lagrangian relaxation technique to solve the MAPs with decomposable costs. But the major contribution was an efficient parallelization of this algorithm on a graphics processing unit (GPU) based programming architecture. Bigger problems with larger data sets were solved by using multiple processors with each having a GPU of its own. This not only handled the data by distributing it among the processors, but also increased the amount of parallelization to give us good iteration times. Problems with 796 million cost variables were solved on varying number of processors between 1 and 64, with significantly fast iteration times. Owing to the good scalability of the developed parallel solver, we successfully solved problems with 31 billion cost variables on processors ranging from 64 to 128 in good amount of time.","abstract_html":"Multidimensional assignment problem (MAP) is one of the many formulations of data association problem which categorizes data based on various data sources. A higher number of data sources ensures an accurate categorization of data. But it also leads to a significant increase in the amount of data, consequently increasing the computation time where quick results are sought. In this work, we used Lagrangian relaxation technique to solve the MAPs with decomposable costs. But the major contribution was an efficient parallelization of this algorithm on a graphics processing unit (GPU) based programming architecture. Bigger problems with larger data sets were solved by using multiple processors with each having a GPU of its own. This not only handled the data by distributing it among the processors, but also increased the amount of parallelization to give us good iteration times. Problems with 796 million cost variables were solved on varying number of processors between 1 and 64, with significantly fast iteration times. Owing to the good scalability of the developed parallel solver, we successfully solved problems with 31 billion cost variables on processors ranging from 64 to 128 in good amount of time.","abstract_has_math":false,"creators":["Natu, Shardul"],"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":2018,"date_issued":"2018-05","date_published":"2018-05","updated_at":"2026-07-22T22:24:38Z","subjects":["Multidimensional assignment problem (MAP)","Linear assignment problem (LAP)","Graphics processing unit (GPU)","Lagrangian relaxation."],"languages":["en"],"rights":["Copyright 2018 Shardul Natu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/101117","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":["Natu, Shardul"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-05","2018-02-23","2018-09-04T20:33:49Z","2020-09-05T09:15:32Z"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"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":["Multidimensional assignment problem (MAP)","Linear assignment problem (LAP)","Graphics processing unit (GPU)","Lagrangian relaxation."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2018 Shardul Natu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/101117"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Multidimensional assignment problem (MAP) is one of the many formulations of data association problem which categorizes data based on various data sources. A higher number of data sources ensures an accurate categorization of data. But it also leads to a significant increase in the amount of data, consequently increasing the computation time where quick results are sought. In this work, we used Lagrangian relaxation technique to solve the MAPs with decomposable costs. But the major contribution was an efficient parallelization of this algorithm on a graphics processing unit (GPU) based programming architecture. Bigger problems with larger data sets were solved by using multiple processors with each having a GPU of its own. This not only handled the data by distributing it among the processors, but also increased the amount of parallelization to give us good iteration times. Problems with 796 million cost variables were solved on varying number of processors between 1 and 64, with significantly fast iteration times. Owing to the good scalability of the developed parallel solver, we successfully solved problems with 31 billion cost variables on processors ranging from 64 to 128 in good amount of time.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2020-05-01","The student, Shardul Natu, accepted the attached license on 2018-02-23 at 08:13.","The student, Shardul Natu, submitted this Thesis for approval on 2018-02-23 at 08:46.","This Thesis was approved for publication on 2018-02-23 at 11:45.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12046 on 2018-08-31 at 17:17:11","Made available in DSpace on 2018-09-04T20:33:49Z (GMT). No. of bitstreams: 3 NATU-THESIS-2018.pdf: 1577475 bytes, checksum: 054de6823911855bb4f782e8dafc6ed9 (MD5) gpu-based-lagrangian.zip: 1476700 bytes, checksum: 549dac78cb851860e8776474df992d2a (MD5) LICENSE.txt: 4209 bytes, checksum: 6359849752f0e389880dd234fffa99b9 (MD5) Previous issue date: 2018-02-23","Embargo set by: Seth Robbins for item 107200 Lift date: 2020-09-04T20:34:13Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 107200 Lift date: 2020-09-04T20:37:00Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 107200 Lift date: 2020-09-04T20:42:08Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 107200 on 2020-09-05T09:15:32Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["GPU-based Lagrangian heuristic for multidimensional assignment problems with decomposable costs"]}]}],"canonical_facts":{"dc:contributor":["Nagi, Rakesh"],"dc:creator":["Natu, Shardul"],"dc:date":["2018-05","2018-02-23","2018-09-04T20:33:49Z","2020-09-05T09:15:32Z"],"dc:description":["Multidimensional assignment problem (MAP) is one of the many formulations of data association problem which categorizes data based on various data sources. A higher number of data sources ensures an accurate categorization of data. But it also leads to a significant increase in the amount of data, consequently increasing the computation time where quick results are sought. In this work, we used Lagrangian relaxation technique to solve the MAPs with decomposable costs. But the major contribution was an efficient parallelization of this algorithm on a graphics processing unit (GPU) based programming architecture. Bigger problems with larger data sets were solved by using multiple processors with each having a GPU of its own. This not only handled the data by distributing it among the processors, but also increased the amount of parallelization to give us good iteration times. Problems with 796 million cost variables were solved on varying number of processors between 1 and 64, with significantly fast iteration times. Owing to the good scalability of the developed parallel solver, we successfully solved problems with 31 billion cost variables on processors ranging from 64 to 128 in good amount of time.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2020-05-01","The student, Shardul Natu, accepted the attached license on 2018-02-23 at 08:13.","The student, Shardul Natu, submitted this Thesis for approval on 2018-02-23 at 08:46.","This Thesis was approved for publication on 2018-02-23 at 11:45.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12046 on 2018-08-31 at 17:17:11","Made available in DSpace on 2018-09-04T20:33:49Z (GMT). No. of bitstreams: 3 NATU-THESIS-2018.pdf: 1577475 bytes, checksum: 054de6823911855bb4f782e8dafc6ed9 (MD5) gpu-based-lagrangian.zip: 1476700 bytes, checksum: 549dac78cb851860e8776474df992d2a (MD5) LICENSE.txt: 4209 bytes, checksum: 6359849752f0e389880dd234fffa99b9 (MD5) Previous issue date: 2018-02-23","Embargo set by: Seth Robbins for item 107200 Lift date: 2020-09-04T20:34:13Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 107200 Lift date: 2020-09-04T20:37:00Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 107200 Lift date: 2020-09-04T20:42:08Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 107200 on 2020-09-05T09:15:32Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/101117"],"dc:language":["en"],"dc:rights":["Copyright 2018 Shardul Natu"],"dc:subject":["Multidimensional assignment problem (MAP)","Linear assignment problem (LAP)","Graphics processing unit (GPU)","Lagrangian relaxation."],"dc:title":["GPU-based Lagrangian heuristic for multidimensional assignment problems with decomposable costs"],"dc:type":["text"],"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:38Z"}