Parallel algorithm design for branch and bound

David A. Bader, William E. Hart, Cynthia A. Phillips

Research output: Chapter in Book/Report/Conference proceedingChapter

12 Scopus citations

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 porting of serial optimization codes to parallel systems and discuss more fundamentally parallel approaches to optimization. We survey the state-of-the-art in distributedand 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.

Original languageEnglish (US)
Title of host publicationInternational Series in Operations Research and Management Science
PublisherSpringer New York LLC
StatePublished - 2005
Externally publishedYes

Publication series

NameInternational Series in Operations Research and Management Science
Volume76
ISSN (Print)0884-8289

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Strategy and Management
  • Management Science and Operations Research
  • Applied Mathematics

Keywords

  • Branch and bound
  • Distributed memory
  • Grid computing
  • Optimization
  • Parallel algorithms
  • Shared memory

Fingerprint

Dive into the research topics of 'Parallel algorithm design for branch and bound'. Together they form a unique fingerprint.

Cite this