Load balancing for parallel branch and bound algorithms

Abstract

In this talk the of parallel branch and bound algorithm template is presented. Branch and bound algorithm is used to solve global optimization problems. Here the minimization problem /• = min f(X) X&D • ' of function /(a;) over the region of feasible solution D is considered. The branch and bound algorithm has a strict structure and the sequential and parallel templates of the algorithm are introduced [3]. The algorithm templates implement general structure of the algorithm and its interaction with particular problem. The problem specific part should be imple¬mented by the template user. For parallel programming, the template also specifys main features of parallel algorithm: partitioning, communication, agglomeration and mapping. The template automatically spawns the processes on available processors, ensures proper communication and syn¬chronization [2]. The branch and bound algorithm template implements algorithms based on initial search space decomposition and distribution among the processors. Using this paradigm, additional processor load balancing is important for better parallel execution [1]. The branch and bound algorithm template was extended with dynamic load balancing module. Module implements several diffusion based dynamic load balancing algorithms that ensures more even load of the processors and better execution of implemented parallel algorithms.