
Chapter 8
GPU-accelerated tree-based exact
optimization methods
Imen Chakroun and Nouredine Melab
University of Lille 1, CNRS/LIFL/INRIA, France
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
8.2 Branch-and-bound algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
8.3 Parallel branch-and-bound algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
8.3.1 The parallel tree exploration model . . . . . . . . . . . . . . . . . . . . . 158
8.3.2 The parallel evaluation of bounds model . . . . . . . . . . . . . . . . 158
8.4 The