Branch-and-bound and parallel computation: A historical note (Q1099088): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 01:31, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Branch-and-bound and parallel computation: A historical note |
scientific article |
Statements
Branch-and-bound and parallel computation: A historical note (English)
0 references
1988
0 references
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.
0 references
parallel processing
0 references
branch-and-bound
0 references
traveling salesman
0 references