Exact algorithmns for combinatorial optimization problems using PUBB – a generalized utility for parallel branch-and-bound algorithms

The branch-and-bound algorithm is mostly applied for solving combinatorial optimization problems exactly. In practice, however, there is a limit of a problem size which can be solved in a reasonable amount of time. Parallelization of the branch-and-bound algorithm is an important approach to solve more problems beyond the limit, and according to the recent advance of parallel machines, much effort has been devoted to the parallelization. Especially, based on the general framework of the branch-and-bound algorithm, generalized tool development is a trend of the implementations. PUBB (Parallelization Utility for Branch-and-Bound algorithms), developed by Shinano et al., is one of the generalized tools. Since the first development of PUBB, several improvements have been made in order to apply to a wide variety of problems, and the current PUBB realizes a central, a distributed and a mixed control scheme of search tree management. In this paper, we provide an outline of PUBB, in which the three control schemes are introduced. We also provide applications of PUBB to classical combinatorial optimization problems, the Travelling Salesman Problem and the Maximum Clique Problem. We are now preparing PUBB available via the Internet, and as an appendix, we give the user interface for PUBB designed with the C language.