On parallel Branch and Bound frameworks for Global Optimization

Juan F. R. Herrera (), José M. G. Salmerón (), Eligius M. T. Hendrix (), Rafael Asenjo () and Leocadio G. Casado ()
Additional contact information
Juan F. R. Herrera: The University of Edinburgh
José M. G. Salmerón: University of Almeria (ceiA3)
Eligius M. T. Hendrix: Universidad de Málaga
Rafael Asenjo: Universidad de Málaga
Leocadio G. Casado: University of Almeria (ceiA3)

Journal of Global Optimization, 2017, vol. 69, issue 3, No 2, 547-560

Abstract: Abstract Branch and Bound (B&B) algorithms are known to exhibit an irregularity of the search tree. Therefore, developing a parallel approach for this kind of algorithms is a challenge. The efficiency of a B&B algorithm depends on the chosen Branching, Bounding, Selection, Rejection, and Termination rules. The question we investigate is how the chosen platform consisting of programming language, used libraries, or skeletons influences programming effort and algorithm performance. Selection rule and data management structures are usually hidden to programmers for frameworks with a high level of abstraction, as well as the load balancing strategy, when the algorithm is run in parallel. We investigate the question by implementing a multidimensional Global Optimization B&B algorithm with the help of three frameworks with a different level of abstraction (from more to less): Bobpp, Threading Building Blocks (TBB), and a customized Pthread implementation. The following has been found. The Bobpp implementation is easy to code, but exhibits the poorest scalability. On the contrast, the TBB and Pthread implementations scale almost linearly on the used platform. The TBB approach shows a slightly better productivity.

Keywords: Branch-and-Bound; Load balancing; Shared-memory; Framework; TBB; 68P05; 68W10; 90C57 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-017-0508-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:69:y:2017:i:3:d:10.1007_s10898-017-0508-y

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-017-0508-y

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().