Assessing the Effectiveness of (Parallel) Branch-and-bound Algorithms
Assessing the Effectiveness of (Parallel) Branch-and-bound Algorithms
复制标题
DOI：
--
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
Stephen J. Maher;T. Ralphs;Y. Shinano
中科院分区：
文献类型：
--
作者：
Stephen J. Maher;T. Ralphs;Y. Shinano
实证研究是评估分支定界算法实现有效性的基础。由于各种原因，这种实现的复杂性使得实证研究变得困难。已经进行了各种尝试，以开发和编纂一套标准的技术，用于评估优化算法及其软件实现，但是，大多数以前的工作一直集中在经典的顺序算法。由于并行计算已成为日益主流，有必要重新审视和现代化这些做法。在本文中，我们提出了一个评估框架的基础上的概念，即资源消耗是我们通常所说的“有效性”的实施的核心。所提出的框架仔细区分实现的基线效率，它利用固定资源分配的效率，以及它的可扩展性，效率如何随着资源（通常是额外的计算核心）的添加或删除而变化的度量。效率通常适用于顺序实现，而可伸缩性适用于并行实现。效率和可伸缩性都是决定给定并行实现的整体有效性的重要因素，但提高效率的目标往往与提高可伸缩性的目标不一致。在拟议的框架内，我们审查的挑战，有效的评价，并讨论现有的评估方法的优点和缺点。
Empirical studies are fundamental in assessing the effectiveness of implementations of branch-and-bound algorithms. The complexity of such implementations makes empirical study difficult for a wide variety of reasons. Various attempts have been made to develop and codify a set of standard techniques for the assessment of optimization algorithms and their software implementations; however, most previous work has been focused on classical sequential algorithms. Since parallel computation has become increasingly mainstream, it is necessary to re-examine and modernize these practices. In this paper, we propose a framework for assessment based on the notion that resource consumption is at the heart of what we generally refer to as the “effectiveness” of an implementation. The proposed framework carefully distinguishes between an implementation’s baseline efficiency, the efficacy with which it utilizes a fixed allocation of resources, and its scalability, a measure of how the efficiency changes as resources (typically additional computing cores) are added or removed. Efficiency is typically applied to sequential implementations, whereas scalability is applied to parallel implementations. Efficiency and scalability are both important contributors in determining the overall effectiveness of a given parallel implementation, but the goal of improved efficiency is often at odds with the goal of improved scalability. Within the proposed framework, we review the challenges to effective evaluation and discuss the strengths and weaknesses of existing methods of assessment.