David A. Bader
IEEE Fellow
AAAS Fellow
Professor
College of Computing
Georgia Tech
Atlanta, GA 30332


 
 

 

Parallel Algorithm Design for Branch and Bound

Large and/or computationally expensive optimization problems sometimes require parallel or high-performance computing systems to achieve reasonable running times. This chapter gives an introduction to parallel computing for those familiar with serial optimization. We present techniques to assist the porting of serial optimization codes to parallel systems and discuss more fundamentally parallel approaches to optimization. We survey the state-of-the-art in distributed- and shared-memory architectures and give an overview of the programming models appropriate for efficient algorithms on these platforms. As concrete examples, we discuss the design of parallel branch-and-bound algorithms for mixed-integer programming on a distributed-memory system, quadratic assignment problem on a grid architecture, and maximum parsimony in evolutionary trees on a shared-memory system.

Publication History

Versions of this paper appeared as:
  1. David A. Bader, William E. Hart, and Cynthia A. Phillips, ``Parallel Algorithm Design for Branch and Bound,''
    in H.J. Greenberg, editor, Tutorials on Emerging Methodologies and Applications in Operations Research, Kluwer Academic Press, Chapter 5, pp. 1-44, 2004.

Download this report in Adobe PDF


 
 

Last updated: October 24, 2004

 




Computational Biology



Parallel Computing



Combinatorics