Branch-and-bound and parallel computation: A historical note
type: Item
instance of: scholarly article
title: Branch-and-bound and parallel computation: A historical note
zbMATH Open document ID: 0637.90097
DOI: 10.1016/0167-6377(88)90067-3
author: E. A. Pruul
author: G. L. Nemhauser
author: Russell A. Rushmeier
published in: Operations Research Letters
publication date: 1988-01-01T00:00:00Z
review text: This historical note summarizes what we believe to have been the first use of parallel processing to solve a combinatorial optimization problem by a branch-and-bound algorithm. In 1975, a branch-and-bound algorithm for the traveling salesman problem that used p parallel processors with shared memory was simulated on a single processor. The results show that the simultaneous exploration of several nodes of the search tree yields better feasible solutions earlier. This allows earlier pruning of branches and significantly reduces the number of nodes searched.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 4039669
zbMATH Keywords: parallel processing
zbMATH Keywords: branch-and-bound
zbMATH Keywords: traveling salesman
MaRDI profile type: Publication
full work available at URL: 0167-6377(88)90067-3
OpenAlex ID: W2003540175
cites work: A simulation tool for the performance evaluation of parallel branch and bound algorithms
cites work: Technical Note—On Partitioning the Feasible Set in a Branch-and-Bound Algorithm for the Asymmetric Traveling-Salesman Problem
cites work: An introduction to parallelism in combinatorial optimization
cites work: Q3221759
cites work: Experiments with parallel algorithms for combinatorial problems
cites work: Anomalies in parallel branch-and-bound algorithms
cites work: Performance of parallel branch-and-bound algorithms
cites work: A note on anomalies in parallel branch-and-bound algorithms with one-to- one bounding functions
cites work: An Algorithm for the Traveling Salesman Problem
cites work: MANIP—A Multicomputer Architecture for Solving Combinatonal Extremum-Search Problems
description: scientific article; zbMATH DE number 4039669