How Much Communication Does Parallel Branch and Bound Need?

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.