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

Vadrevu, Samhita

Permalink

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

Description

Title

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

Author(s)

Vadrevu, Samhita

Issue Date

2023-04-17

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

Nagi, Rakesh

Doctoral Committee Chair(s)

Nagi, Rakesh

Committee Member(s)

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

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Multi-Dimensional Assignment, Quadratic Assignment, Clique-Partitioning, High performance computing (HPC), Graphics processing units (GPU), Compute unified device architecture (CUDA)

Abstract

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.

Graduation Semester

2023-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Samhita Vadrevu

Owning Collections