PUBB2: A Redesigned Object-oriented Software Tool for Implementing Parallel and Distributed Branch-and-Bound Algorithms*

Y. Shinano, T. Fujie, and Y. Kounoike (Japan)


Branch-and-Bound, Parallel and Distributed Computing, Software Tool


PUBB (Parallelization Utility for Branch-and-Bound algo rithms) is a software tool developed to provide a general framework for deploying sequential/parallel branch-and bound algorithms. In this paper, PUBB was redesigned and renamed to PUBB2. Recently, sophisticated general frame works for parallel branch-and-cut algorithms have been de veloped. Many of them have well defined but relatively large and complicated interfaces. The main goal of PUBB2 is to provide a small building block software tool with an extendable core, which is flexible enough to construct a variety of frameworks for parallelization of branch-and bound algorithms. The software architecture of PUBB2 is introduced and its flexibility is demonstrated. In order to show how a framework can be built using PUBB2, an implementation of a simple parallelization algorithm for branch-and-bound is given as an example. Preliminary computational results using the constructed framework for the maximum clique problem are also presented.

Important Links:

Go Back