GPU-accelerated solutions for higher-order assignment and graph partition problems

Applications of integer programming models are wide-spread, ranging from management (resource allocation, scheduling, facility location) to scientific applications (molecular biology, high-energy physics) [139]. However, a majority of these problems are NP-Hard and exact algorithms are not scalable. In this dissertation, an efficient and scalable framework is proposed to solve a class of integer programs, and is demonstrated using three prominent real-world applications. These problems are: (1) Multi-Target Tracking application formulated as the Multi-dimensional Assignment Problem (MAP), (2) facility location as the Quadratic Assignment Problem (QAP), and (3) the entity resolution problem formulated as a Clique Partitioning Problem (CPP). Firstly, a dual-ascent-based technique is proposed to solve MAP near-optimally. It is accompanied by a gap closure scheme to find provably optimal solutions. This algorithm can handle significantly large problems of up to 25 billion variables. Secondly, the QAP is approached from a maximum entropy perspective. A Sinkhorn algorithm is employed to find strong lower bounds to the linearized QAP and is equipped to handle problems of size 50 with memory complexity O(N6), translating to 15 billion edges. Lastly, a two-phase approach is proposed to solve the clique partitioning problem, where the first phase is to find maximal cliques in the graph, and the second phase is translated into a generalized set packing model. A novel formulation is proposed as a superior alternative to the traditional set-packing formulation in terms of memory efficiency. It is solved approximately using a GPU-accelerated and scalable heuristic and integrated with an exact parallel branch-and-bound scheme, providing provable optimal solutions.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Vadrevu, Samhita

Contributors dc:contributor

• Nagi, Rakesh
• Sreenivas, Ramavarapu
• Etesami, Rasoul
• Patel, Sanjay

• Multi-dimensional Assignment
• Quadratic Assignment
• Clique-partitioning
• High Performance Computing (HPC)
• Graphics Processing Units (GPU)
• Compute Unified Device Architecture (CUDA)

Statement dc:rights

• Copyright 2023 Samhita Vadrevu

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/120506

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F120506