University of Paderborn
Department of Computer Science

Portable Parallel Branch-and-Bound Library


University of Paderborn Research Group Prof.Dr.B.Monien


The 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:

We are always looking forward for porting the library to different systems than listet above using the given software environments.

To request a library version skip to section Request Library. For a detailed description of the library see the subsections of section Documentation, especially the User Manual of PPBB-Lib.

Back to list of contents


Back to list of contents

Download PPBB-Lib


The research of the following papers was done with the help of the library:

Back to list of contents

Contact, Comments, and Questions

If you have any comments or questions concerning the PPBB-Library, plaese do not hesitate to send a message to one of the following addresses:


c/o Norbert Sensen
University of Paderborn
Dept. of Computer Science
Fuerstenallee 11
33102 Paderborn, Germany
Phone +49 +5251 60-6728
Fax +49 +5251 60-6697


Back to list of contents

written by , last modified 2001, Dec, 20th