How much communication does parallel branch and bound need?

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


Consider the classical branch and bound algorithm for mixed integer programming (MIP). Parallel implementations of this method are known to be viable and reasonably scalable on systems with sophisticated, high-performance interprocessor communication capabilities. But how parallel can the algorithm be when communication is more rudimentary? This article attempts to address this question by comparing two different implementations of MIP branch and bound on CM-5 systems with between 4 and 64 processors, using a selection of MIPLIB test problems. The first code, CMMIP, exploits many of the advanced features of the CM-5 network, whereas the second, called LCMIP, has a minimal, relatively infrequent communication pattern. Generally speaking, the performance of the low-communication code Is competitive for relatively difficult problems and/or small processor configurations, but it appears that advanced communications features are essential to extract the maximum degree of parallelism from a given problem Instance.

Original languageEnglish (US)
Pages (from-to)15-29
Number of pages15
JournalINFORMS Journal on Computing
Issue number1
StatePublished - 1997

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research


  • Interprocessor communication issues
  • Parallel
  • Parallel implementation


Dive into the research topics of 'How much communication does parallel branch and bound need?'. Together they form a unique fingerprint.

Cite this