A generalized utility for parallel branch and bound algorithms

Branch and bound algorithms are general methods applied to various combinatorial optimization problems. Recently, parallelizations of these algorithms have been proposed. In spite of the generality of these methods, many of the parallelizations have been set up for a specific problem and a specific parallel computer. A generalized utility PUBB (Parallelization Utility for Branch and Bound algorithms) is presented. It can be used on a network of workstations and enables us to easily apply parallelized branch and bound algorithms on any specific combinatorial optimization problem. A new selection rule (hybrid selection rule) was implemented during this study. Several branch and bound algorithms were experimentally parallelized with PUBB, using up to 111 networked workstations. The results of these experiments show that superlinear speedup in solving time may be achieved when the number of processing elements is increased and also indicate that the hybrid selection rule has an advantage over other selection rules