Parallelizing Branch-and-Bound on GPUs for Optimization of Multiproduct Batch Plants

Borisenko A, Haidl M, Gorlatch S

Zusammenfassung

Parallel implementation of the Branch-and-Bound (B&B)technique for optimization problems is a promising approach to accel-erating their solution, but it remains challenging on Graphics ProcessingUnits (GPUs) due to B&B's irregular data structures and poor computa-tion/communication ratio. The contributions of this paper are as follows:1) we develop two basic implementations (iterative and recursive) of B&Bon systems with GPUs for a practical application scenario - optimal de-sign of multi-product batch plants; 2) we propose and implement severaloptimizations of our CUDA code using both algorithmic techniques ofreducing branch divergence and GPU-specific properties of the memoryhierarchy; and 3) we evaluate our implementations and optimizations ona modern GPU-based system and we report our experimental results.