Optimization Online


Assessing the Effectiveness of (Parallel) Branch-and-bound Algorithms

Stephen J Maher(s.j.maher***at***exeter.ac.uk)
Ted K Ralphs(ted***at***lehigh.edu)
Yuji Shinano(shinano***at***zib.de)

Abstract: 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.

Keywords: effectiveness, efficiency, performance, scalability, algorithm assessment, branch-and- bound, benchmarking

Category 1: Integer Programming

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: ZIB Report 19-03, Zuse Institute Berlin

Download: [PDF]

Entry Submitted: 09/25/2019
Entry Accepted: 09/25/2019
Entry Last Modified: 09/25/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society