Parallel, Lock-Free Framework for Decision Diagram (DD) based Search

This thesis presents the development of a parallel Decision Diagram-based Benders Decomposition (DD-BD) solver for stochastic mixed-integer programming and introduces a new lock-free work-stealing algorithm designed to overcome its scheduling bottlenecks. Existing work-stealing queues performed inefficiently for solver workloads involving bulk node generation and single-stealer concurrency. To address this, an unbounded queue supporting native bulk push and steal operations was developed, achieving lock-free progress and constant-latency performance. Benchmarks show significant improvements over state-of-the-art implementations such as C++ Taskflow. The algorithm has been integrated into the solver’s parallel framework, forming the foundation for further work on adaptive load balancing and distributed scalability in large-scale stochastic optimization.

Committee: Danial Davarni (co-major professor), Ali Jannesari (co-major professor), and Liyi Li