H-B&B: A Hierarchical B&B for large scale environments
Loading...
Date
2011-05-25
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this paper, we propose a parallel B&B (H-B&B) based on the Hierarchical Master/Worker paradigm. It aims at improving the scalability of the traditional M/W-based B&Bs (M/W-B&B) eliminating the bottlenecks created on the central master process. Unlike the state-of-the-art approaches, H-B&B is fully dynamic as it is composed of several levels of masters, and evolves over time according to the dynamic acquisition of new computing nodes and their disconnections. To evaluate our approach we propose three execution scenarios. First, we evaluate the ability of H-B&B to scale-up and deploy a huge number of nodes. Second, we evaluate its efficiency and its ability to avoid bottlenecks. Finally, we evaluate its ability to scale-down and to manage the release of a part or the votality of the nodes.
Description
Keywords
Master–worker; Hierarchical master–worker; Grid computing; Branch and bound; Large scale experiments