PARALLEL MPI-IMPLEMENTATION OF THE BRANCH-AND-BOUND ALGORITHM FOR OPTIMAL SELECTION OF PRODUCTION EQUIPMENT
Andrey Borisenko, Sergei Petrovich Gorlatch, Westfälische Wilhelms-Universität, Münster, Germany · Вестник Тамбовского государственного технического университета · 2016
In this paper, we propose a parallel implementation of the branch-andbound optimization technique on distributed-memory systems using Message Passing Interface (MPI).We employ parallel branch-and-bound to accelerate a real-world example application: optimal selection of production equipment for multi-product batch plants.We describe the master-worker organization of our parallel algorithm: a single master process dispatches a subset of computations to multiple worker processes and gathers computed results from them.For exchanging messages between master and worker we use MPI's point-to-point communication functions.We report experimental results about the speedup and efficiency of our parallel implementation.We observe that the master process may become a bottleneck for the overall application performance if it controls too many workers processes, because of the increasing communication overhead.