A strategy for parallelization of a state-of-the-art Branch and Bound algorithm for weighted CSPs and other graphical model optimization tasks is introduced: independent worker nodes concurrently solve subproblems, managed by a Branch and Bound master node; the problem cost functions are used to predict subproblem complexity, enabling efficient load balancing, which is crucial for the performance of the parallelization process. Experimental evaluation on up to 20 nodes yields very promising results and suggests the effectiveness of the scheme. The system runs on loosely coupled commodity hardware, simplifying deployment on a larger scale in the future.