Optimization Online


MW: A Software Framework for Combinatorial Optimization on Computational Grids

Wasu Glankwamdee (wag3***at***lehigh.edu)
Jeff Linderoth (jtl3***at***lehigh.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


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society