Load balancing in solving problems based on estimates of the computational complexity of subproblems

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.