Towards GPU-accelerated discrete optimization

Kawtikwar, Samiran

Permalink

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

Description

Title

Towards GPU-accelerated discrete optimization

Author(s)

Kawtikwar, Samiran

Issue Date

2025-12-01

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

Nagi, Rakesh

Doctoral Committee Chair(s)

Nagi, Rakesh

Committee Member(s)

• Lumetta, Steven S
• Hajj, Izzat El
• Hanasusanto, Grani A

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• High-performance computing
• Linear assignment problem
• Branch-and-Bound
• Graphics Processing Units
• LP Crossover
• Parallel algorithms
• CUDA
• Optimization
• GPU priority queues

Abstract

Discrete optimization plays a crucial role in solving complex decision-making problems across a wide range of applications in operations research. These problems often involve selecting an optimal subset or sequence of decisions from a finite set, a task that becomes exponentially harder as the problem size grows. While traditional computing approaches are powerful, they often struggle to meet the time and computational demands of large-scale discrete optimization problems, where even finding near-optimal solutions can be highly resource-intensive. With the advent of High-Performance Computing (HPC), we are now equipped to tackle large and complex optimization problems that were previously infeasible. However, most discrete optimization algorithms remain inherently sequential and are not designed to fully exploit modern hardware accelerators, such as Graphics Processing Units (GPUs), which now constitute a significant portion of the modern HPC infrastructure. Primarily known for their use in graphics rendering and artificial intelligence, we show that GPUs can also be used to accelerate discrete optimization algorithms. This enables solutions to large and complex optimization problems while efficiently using modern HPC hardware. This work is a culmination of knowledge in parallel programming, discrete optimization, and GPU architecture, which results in significant performance improvements. We focus on different aspects of discrete optimization, such as bound computations, Branch-and-Bound search, and linear programming, all of which are critical for solving these problems, particularly Mixed Integer Linear Programs (MILPs). First, for bound computations, we develop HyLAC (Hybrid Linear Assignment solver in CUDA), the fastest known GPU-based solver for the Linear Assignment Problem (LAP). LAP is a fundamental combinatorial optimization problem with applications in tracking, scheduling, and resource allocation. HyLAC combines GPU-accelerated classical and tree Hungarian algorithms and dynamically switches between them based on solution progress, improving the performance of both sparse and dense LAP instances. HyLAC outperforms the state-of-the-art GPU LAP solvers by up to 6.14x. The tiled version of HyLAC, which is useful in many real-world applications, is geomean 22.59x faster than existing solutions. HyLAC is open-sourced and has been integrated into the NVIDIA RAPIDS library, making it accessible to a wide range of users. Second, for Branch-and-Bound (BnB) search, we introduce the first fully GPU-resident Best-First Search (BeFS) based BnB framework. Traditional GPU BnB approaches have been limited to Breadth-First or Depth-First traversal due to the difficulty of implementing concurrent priority queues on massively parallel architectures. We overcome this challenge by developing a master-worker-based concurrent priority queue, dynamic memory management strategies for subproblem storage, and a message-passing mechanism that enables efficient exploration of the search tree within a single GPU kernel. This results in a highly efficient bnb framework that combines node and tree parallelism, achieving total speedups up to 438.1x over single-threaded CPU implementations, when solving the Resource Constrained Assignment Problem (RCAP) and the Quadratic Assignment Problem (QAP). Third, we develop the first GPU-accelerated crossover algorithm to convert interior point or first-order Linear Programming (LP) solutions into precise vertex solutions, with optimal primal and dual basis. Crossover is a key bottleneck in modern MILP solvers, yet it remains inherently sequential due to its dependence on iterative simplex pivots. A recently proposed crossover algorithm exploits the spiral dynamics of Primal-Dual Hybrid Gradient (PDHG) based methods to perform vertex recovery without simplex pivots. We adapt this algorithm to GPUs and achieve significant speedups to this algorithm by improving the auxiliary problem-solving steps and performing better quality primal and dual pushes with parallelism. Overall, this novel crossover algorithm achieves a geomean 14.6x speedups over NETLIB LPs. Together, our contributions demonstrate the significant potential of GPUs in accelerating discrete optimization algorithms. The methodologies developed in this dissertation push the boundary of what is achievable on GPUs and motivate further research in this area at the intersection of discrete optimization and parallel computing. Our implementations are publicly available and aim to catalyze future work in this emerging and impactful field.

Graduation Semester

2025-12

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2025 Samiran Kawtikwar

Owning Collections