Towards a taxonomy of parallel branch and bound algorithms

Abstract

In this paper we present a classification of parallel branch and bound algorithms, and elaborate on the consequences of particular parameter settings. The taxonomy is based upon how the algorithms handle the knowledge about the problem instance to be solved, generated during execution. The starting point of the taxonomy is the generally accepted description of the sequential branch and bound algorithm, as presented in, for example, [Mitten 1970] and [Ibaraki 1976a, 1976b, 1977a, 1977b]. 1980 Mathematical Subject Classification: 90C27, 68Q10, 68R05. Key Words & Phrases: branch and bound, taxonomy, parallelism, nondeterminism, asynchronicity. 1. THE BRANCH AND BOUND ALGORITHM Branch and bound algorithms solve optimization problems by partitioning the solution space. Throughout this paper, we will assume that all optimization problems are posed as minimization problems, and that solving a problem is tantamount to finding a feasible solution with minimal value. If there are many such s...