WCSE 2015
ISBN: 978-981-09-5471-0 DOI: 10.18178/wcse.2015.04.020

Complexity Based Load Balancing for Distributed Branch and Bound Method

Bo Tian, Mikhail Posypkin

Abstract— We proposed a new static load distribution strategy for parallel Branch-and-Bound method based on complexity estimates of sub-problems appearing in a Branch-and-Bound tree. This strategy can be used on parallel systems with low connectivity where dynamic load balancing is problematic. The experimental results demonstrated the superiority of the proposed strategy over other three strategies under test. Based on these results we draw some conclusions about the duration of the first (serial) part of the algorithm and choice of a load distribution strategy.

Index Terms— Branch-and-Bound, Parallel Computing, Load Balance.

Bo Tian, Mikhail Posypkin
Lomonosov Moscow State University, Institute for Information Transmission Problems of RAS, RUSSIA


Cite: Bo Tian, Mikhail Posypkin, "Complexity Based Load Balancing for Distributed Branch and Bound Method," 2015 The 5th International Workshop on Computer Science and Engineering-Information Processing and Control Engineering (WCSE 2015-IPCE), pp. 124-129, Moscow, Russia, April 15-17, 2015.