Parallel Branch and Bound Algorithms on Internet Connected Workstations

Abstract. By the use of the GRIBB software for distributed computing across the Internet, we are investigating the obstacles and the potential for efficient parallelization of Branch and Bound algorithms. Experiments have been carried out using two different applications, i.e. the Quadratic Assignment Problem (QAP) and the Traveling Salesman Problem (TSP). The results confirm the potential of the approach, and underline the requirements of the problem, algorithm and architecture for the approach to be successful.