Distributed versus Centralized Storage and Control for Parallel Branch and Bound: Mixed Integer Programming on the CM-5

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)199-220
Number of pages22
JournalComputational Optimization and Applications
Volume7
Issue number2
DOIs
StatePublished - 1997

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

Keywords

  • Branch and bound methods
  • Mixed integer programming
  • Parallel computing

Fingerprint

Dive into the research topics of 'Distributed versus Centralized Storage and Control for Parallel Branch and Bound: Mixed Integer Programming on the CM-5'. Together they form a unique fingerprint.

Cite this