Abstract
In this paper we present a probabilistic model for analysing trees generated during problem solving using best-first search Branch and Bound algorithm. We consider the weight associated with the edges as well as the number of children in a node to be random. The expressions obtained for the sequential algorithm are applied to several parallel strategies using a multiprocessor with distributed memory.
This work was supported in part by the MES (CICYT) of Spain under contract TIC96-1125-C03, Xunta de Galicia XUGA20605B96 and EC project BRPR-CT96-01070. The authors would like to thank Fujitsu Parallel Computing Research Centre for making an account on the AP1000 multicomputer available to us.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. K. Yang and C. R. Das, “Evaluation of a Parallel Branch-and-Bound Algorithm on a Class of Multiprocessors”. IEEE Trans. on Parallel and Distributed Systems. vol. 5, No. 1, pp. 74–86. January 1994.
D. R. Smith, “Random Trees and the Analysis of Branch and Bound Procedures”, J. of the ACM, vol. 31, No. 1, pp. 163–168, January 1984.
T. E. Harris, The Theory of Branching Processes, Dover Publications, Inc, New York, 1989.
M.H. Willebeek-LeMair and A.P. Reeves. “Strategies for Dynamic Load Balancing on Highly Parallel Computers”. IEEE Transactions on parallel and distributed processing, vol. 4, No. 9, pp. 979–993, 1993.
R. Correa and A. Ferreira, “A Distributed Implementation of Asyncronous Parallel Branch and Bound”. In Ferreira and J.D.P. Rolim (eds.), Parallel Algorithms for Irregular Problems (pp. 157–176), Kluwer Academic, 1995.
C.G. Diderich and M. Gengier, “Experiments with a parallel synchronized Branch and Bound algorithm”. In Ferreira and J.D.P. Rolim (eds.), Parallel Algorithms for Irregular Problems (pp. 177–193), Kluwer Academic, 1995.
Y. Zhang, “Parallel Algorithms for Combinatorial Search Problems”, PhD. Thesis, University of California at Berkley, 1989.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Argüello, F., Guil, N., López, J., Amor, M., Zapata, E.L. (1997). A probabilistic model for best-first search B&B algorithms. In: Bilardi, G., Ferreira, A., Lüling, R., Rolim, J. (eds) Solving Irregularly Structured Problems in Parallel. IRREGULAR 1997. Lecture Notes in Computer Science, vol 1253. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63138-0_5
Download citation
DOI: https://doi.org/10.1007/3-540-63138-0_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63138-5
Online ISBN: 978-3-540-69157-0
eBook Packages: Springer Book Archive