Parallel Algorithm Design for Branch and Bound

David A. Bader (), William E. Hart () and Cynthia A. Phillips ()
Additional contact information
David A. Bader: University of New Mexico
William E. Hart: Sandia National Laboratories
Cynthia A. Phillips: Sandia National Laboratories

Chapter Chapter 5 in Tutorials on Emerging Methodologies and Applications in Operations Research, 2005, pp 5-1-5-44 from Springer

Abstract: Abstract 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 posting 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 sharedmemory system.

Keywords: parallel algorithms; optimization; branch and bound; distributed memory; shared memory; grid computing (search for similar items in EconPapers)
Date: 2005
References: Add references at CitEc
Citations: View citations in EconPapers (4)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-0-387-22827-3_5

Ordering information: This item can be ordered from
http://www.springer.com/9780387228273

DOI: 10.1007/0-387-22827-6_5

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().