Analytical modeling of a parallel branch-and-bound algorithm on MIN-based multiprocessors

In this paper, we propose a parallel `Decomposite Best-First' search Branch-and-Bound algorithm (pdbsbb) for MIN-based multiprocessors. We start with a new probabilistic model to estimate the number of evaluated nodes for a serial algorithm. The proposed algorithm initially decomposes a problem into several subproblems. Each processor executes the serial Best-First search to find a local feasible solution. The local solutions are broadcasted through the network to compute the final solution. The speed-up analysis considers both the computation and communication overheads. It is seen that the parallel Decomposite Best-First search algorithm performs better than other reported schemes when communication overhead is taken into consideration.