On parallel Branch and Bound frameworks for Global Optimization
On parallel Branch and Bound frameworks for Global Optimization
复制标题
全局优化的并行分支定界框架
DOI：
10.1007/s10898-017-0508-y
复制
发表时间：
2017
影响因子：
1.8
通讯作者：
L. G. Casado
中科院分区：
文献类型：
--
作者：
Juan F. R. Herrera;J. M. Salmerón;E. Hendrix;R. Asenjo;L. G. Casado
众所周知，分支定界 (B&B) 算法会表现出搜索树的不规则性。因此，为此类算法开发并行方法是一个挑战。 B&B 算法的效率取决于所选择的分支、边界、选择、拒绝和终止规则。我们研究的问题是所选的由编程语言、使用的库或框架组成的平台如何影响编程工作和算法性能。当算法并行运行时，对于具有高抽象级别的框架以及负载平衡策略，选择规则和数据管理结构通常对程序员隐藏。我们通过在具有不同抽象级别（从多到少）的三个框架的帮助下实现多维全局优化 B&B 算法来研究这个问题：Bobpp、线程构建块 (TBB) 和定制的 Pthread 实现。已发现以下情况。 Bobpp 实现很容易编码，但可扩展性最差。相比之下，TBB 和 Pthread 实现在所使用的平台上几乎呈线性扩展。 TBB 方法显示出稍高的生产率。
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.