Our goal in this paper is to demonstrate that branch-and-bound algorithms for combinatorial optimization can be effectively implemented on a relatively new type of multiprocessor platform known as a computational grid. We will argue that to easily and effectively harness the power of computational grids for branch-and-bound algorithms, the master-worker paradigm should be used to control the algorithm. While recognizing that the master-worker paradigm is inherently not scalable, we will also show that the manner in which the tree search is performed can have a significant impact on the resulting parallel branch-and-bound algorithm's scalability and efficiency. We will also briefly describe a software framework MW that can ease an application developer's burden when implementing master-worker based parallel algorithms on computational grids. We will focus specifically on features of MW that are of the most utility to users wishing to implement branch-and-bound algorithms. To illustrate the impact of the issues we discuss, the paper ends with a case study implementation of a branch-and-bound solver to solve the 0-1 knapsack problem running on a wide-area computational grid of hundreds of processors.
Article
View MW: A Software Framework for Combinatorial Optimization on Computational Grids