ISBN: 978-981-09-5471-0 DOI: 10.18178/wcse.2015.04.020
Complexity Based Load Balancing for Distributed Branch and Bound Method
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.