On parallel Branch and Bound frameworks for Global Optimization

Juan F.R. Herrera, José M.G. Salmerón, Eligius M.T. Hendrix, Rafael Asenjo, Leocadio G. Casado

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

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.
LanguageEnglish
Pages547-560
JournalJournal of Global Optimization
Volume69
Issue number3
Early online date10 Mar 2017
DOIs
Publication statusPublished - Nov 2017

Fingerprint

Branch-and-bound
Global optimization
Global Optimization
Building Blocks
Selection Rules
Search Trees
Irregularity
Data Management
Computer programming
Skeleton
Rejection
Load Balancing
Termination
Computer programming languages
Information management
Productivity
Resource allocation
Programming Languages
Framework
Scalability

Keywords

  • Branch-and-Bound
  • Framework
  • Load balancing
  • Shared-memory
  • TBB

Cite this

Herrera, Juan F.R. ; Salmerón, José M.G. ; Hendrix, Eligius M.T. ; Asenjo, Rafael ; Casado, Leocadio G. / On parallel Branch and Bound frameworks for Global Optimization. In: Journal of Global Optimization. 2017 ; Vol. 69, No. 3. pp. 547-560.
@article{1082fdd9ea984566a78894bf43723b5e,
title = "On parallel Branch and Bound frameworks for Global Optimization",
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, Framework, Load balancing, Shared-memory, TBB",
author = "Herrera, {Juan F.R.} and Salmer{\'o}n, {Jos{\'e} M.G.} and Hendrix, {Eligius M.T.} and Rafael Asenjo and Casado, {Leocadio G.}",
year = "2017",
month = "11",
doi = "10.1007/s10898-017-0508-y",
language = "English",
volume = "69",
pages = "547--560",
journal = "Journal of Global Optimization",
issn = "0925-5001",
publisher = "Springer Verlag",
number = "3",

}

On parallel Branch and Bound frameworks for Global Optimization. / Herrera, Juan F.R.; Salmerón, José M.G.; Hendrix, Eligius M.T.; Asenjo, Rafael; Casado, Leocadio G.

In: Journal of Global Optimization, Vol. 69, No. 3, 11.2017, p. 547-560.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - On parallel Branch and Bound frameworks for Global Optimization

AU - Herrera, Juan F.R.

AU - Salmerón, José M.G.

AU - Hendrix, Eligius M.T.

AU - Asenjo, Rafael

AU - Casado, Leocadio G.

PY - 2017/11

Y1 - 2017/11

N2 - 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.

AB - 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.

KW - Branch-and-Bound

KW - Framework

KW - Load balancing

KW - Shared-memory

KW - TBB

U2 - 10.1007/s10898-017-0508-y

DO - 10.1007/s10898-017-0508-y

M3 - Article

VL - 69

SP - 547

EP - 560

JO - Journal of Global Optimization

T2 - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 3

ER -