MW: A Software Framework for Combinatorial Optimization on Computational Grids

Wasu Glankwamdee (wag3lehigh.edu)
Jeff Linderoth (jtl3lehigh.edu)

Abstract: 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.

Keywords: Computational Grid, Knapsack Problem, Branch and Bound, Master-Worker

Category 1: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 2: Combinatorial Optimization

Citation:

Download: [PDF]

Entry Submitted: 11/11/2005
Entry Accepted: 11/14/2005
Entry Last Modified: 11/11/2005

Modify/Update this entry