Mk. Yang et Cr. Das, EVALUATION OF A PARALLEL BRANCH-AND-BOUND ALGORITHM ON A CLASS OF MULTIPROCESSORS, IEEE transactions on parallel and distributed systems, 5(1), 1994, pp. 74-86
Citations number
16
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
In this paper, we propose and evaluate a parallel ''decomposite best-f
irst'' search branch-and-bound algorithm (dbs) for MIN-based multiproc
essor systems. We start with a new probabilistic model to estimate the
number of evaluated nodes for a serial best-first search branch-and-b
ound algorithm. This analysis is used in predicting the parallel algor
ithm speed-up. The proposed algorithm initially decomposes a problem i
nto N subproblems, where N is the number of processors available in a
multiprocessor. Afterwards, each processor executes the serial best-fi
rst search to find a local feasible solution. Local solutions are broa
dcasted through the network to compute the final solution. A conflict-
free mapping scheme, known as the step-by-step spread, is used for sub
problem distribution on the MIN. A speedup expression for the parallel
algorithm is then derived using the serial best-first search node eva
luation model. Our analysis considers both computation and communicati
on overheads for providing realistic speed-up. Communication modeling
is also extended for the parallel global best-first search technique.
All the analytical results are validated via simulation. For large sys
tems, when communication overhead is taken into consideration, it is o
bserved that the parallel decomposite best-first search algorithm prov
ides better speed-up compared to other reported schemes.