Portable Parallel Branch-and-Bound Library
IntroductionThe Portable Parallel Branch-and-Bound Library ( PPBB-Library ) presents an easy way to parallelize sequential Branch-and-Bound algorithms for several architectures. A user of the library, who wants to run his sequential algorithm on a parallel system, needs neither knowledge about the hardware architecture nor the parallelization mechanisms.
Each parallel running process of the Branch-and-Bound application maintains the point of view of the sequential algorithm. The library overtakes the management of the subproblems, which are created during execution of the Branch-and-Bound algorithm. Load balancers provided by the library take care of a balanced distribution of the subproblems.
The quality of the load balancing strategy is essential for the parallel performance of a sequential efficient Branch-and-Bound algorithm. The user of the library is able to implement own load balancing strategies instead of using the application-independent load balancing algorithms included in the library.
Thus, on the first hand the library can be used for the automatic parallelization of sequential Branch-and-Bound algorithms. On the other hand it can be used for implementing and testing load balancing strategies while the loads are provided by a particular Branch-and-Bound application.
The library is designed to run on any distributed memory multicomputer architecture using the given message passing functions and is written in C.
The library is available for the following software environments and computing platforms at the moment:
updated by Norbert Sensen Okt/20/1997