Distributed versus centralized storage and control for parallel branch and bound: Mixed integer programming on the CM-5

This paper describes parallel, non-shared-memory implementation of the classical general mixed integer branch and bound algorithm, with experiments on the CM-5 family of parallel processors. The main issue in such an implementation is whether task scheduling and certain data-storage functions should be handled by a single processor, or spread among multiple processors. The centralized approach risks creating processing bottlenecks, while the more decentralized implementations differ more from the fundamental serial algorithm. Extensive computational tests on standard MIPLIB problems compare centralized, clustered, and fully decentralized task scheduling methods, using a novel combination of random work scattering and rendezvous-based global load balancing, along with a distributed ‘control by token’ technique. Further experiments compare centralized and distributed schemes for storing heuristic ‘pseudo-cost’ branching data. The distributed storage method is based on continual asynchronous reduction along a tree of redundant storage sites. On average, decentralized task scheduling appears at least as effective as central control, but pseudo-cost storage should be kept as centralized as possible.