Dynamic and hierarchical load-balancing techniques applied to parallel branch-and-bound methods

Most Lipschitzian Global Optimization algorithms perform an exhaustive search using a branch-and-bound (B&B) scheme. The question is how to run multi-dimensional Lipschitz Global Optimization in parallel, such that the implementation depending on the used platform is efficient. Previous work shows a parallel version developed for multicore nodes with two levels of parallelism: intra-node and inter-node. On intra-node level, one can perform dynamic load balancing by generating threads dynamically. Threads end when they complete their assigned work. The inter-node level carries out a static load balancing using MPI. In general, algorithm design depends on the characteristics of problems to be solved. There are several ways to improve performance of general parallel B&B algorithms. Specifically, we are interested in how to apply them to parallel Lipschitz Global Optimization algorithms. Operations like selecting the next subproblem to be evaluated become critical in parallel B&B schemes. We study Depth and Hybrid (Best-Depth) options as selection criterion. Previous work, using only MPI or OpenMP, discard not only the broadcasting of the best found upper bound of the solution due to its high average cost/performance but also the use of dynamic load balancing. Here we check how broadcasting the upper bound affects the developed MPI-Pthreads algorithm. Additionally, we study how to perform dynamic load balancing at inter-node level. Experimental results show which designs perform better on which type of instances for the used computational architecture.