Parallel branch and bound and anomalies

Abstract

In this paper we present a classification of parallel branch and bound algorithms and investigate the anomalies which can occur during the execution of such algorithms. We develop sufficient conditions to prevent deceleration anomalies from degrading the performance. Such conditions were already known for some synchronous cases. It turns out that these conditions can be generalized to arbitrary cases. Finally we develop necessary conditions for acceleration anomalies to improve upon the performance. 1980 Mathematical Subject Classification: 90C27, 68Q10, 68R05. Key Words & Phrases: parallel computer, branch and bound, nondeterminism, asynchronicity, anomalies. Note: This paper will be submitted for publication elsewhere. 1. INTRODUCTION There always is a need for more powerful computers. On one hand we want to solve problems faster than can be done now, on the other hand we want to solve problems which are too big for the computers we have today. Under the traditional model of comp...