Branch-and-bound and parallel computation: A historical note (Q1099088): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
m rollbackEdits.php mass rollback Tag: Rollback |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0167-6377(88)90067-3 / rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2003540175 / rank | |||
Revision as of 07:21, 20 March 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
