Best-first branch-And-bound on a hypercube

Edward William Felten

doi:10.1145/63047.63107

Best-first branch-And-bound on a hypercube

Edward William Felten

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

14 Scopus citations

Abstract

The branch-And-bound technique is a common method for finding exact solutions to difficult problems in combinatorial optimization. This paper will discusss issues surrounding implementation of a particular branch-And-bound algorithm for the traveling-salesman problem on a hypercube multicomputer. The natural parallel algorithm is based on a number of asynchronous processes which interact through a globally shared list of unfinished work. In a distributed-memory environment, we must find a non-centralized version of this shared data structure. In addition, detecting termination of the computation is tricky; an algorithm will be presented which ensures proper termination. Finally, issues affecting performance will be discussed.

Original language	English (US)
Title of host publication	Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988
Editors	Geoffrey Fox
Publisher	Association for Computing Machinery, Inc
Pages	1500-1504
Number of pages	5
Volume	2
ISBN (Electronic)	0897912780, 9780897912785
DOIs	https://doi.org/10.1145/63047.63107
State	Published - Jan 3 1989
Externally published	Yes
Event	3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988 - Pasadena, United States Duration: Jan 19 1988 → Jan 20 1988

Other

Other	3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988
Country/Territory	United States
City	Pasadena
Period	1/19/88 → 1/20/88

All Science Journal Classification (ASJC) codes

Hardware and Architecture
Computer Graphics and Computer-Aided Design
Software
Computer Science Applications

Access to Document

10.1145/63047.63107

Cite this

@inproceedings{3785015fcdc14139b4f54dc1b6681c6f,

title = "Best-first branch-And-bound on a hypercube",

abstract = "The branch-And-bound technique is a common method for finding exact solutions to difficult problems in combinatorial optimization. This paper will discusss issues surrounding implementation of a particular branch-And-bound algorithm for the traveling-salesman problem on a hypercube multicomputer. The natural parallel algorithm is based on a number of asynchronous processes which interact through a globally shared list of unfinished work. In a distributed-memory environment, we must find a non-centralized version of this shared data structure. In addition, detecting termination of the computation is tricky; an algorithm will be presented which ensures proper termination. Finally, issues affecting performance will be discussed.",

author = "Felten, {Edward William}",

year = "1989",

month = jan,

day = "3",

doi = "10.1145/63047.63107",

language = "English (US)",

volume = "2",

pages = "1500--1504",

editor = "Geoffrey Fox",

booktitle = "Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988",

publisher = "Association for Computing Machinery, Inc",

note = "3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988 ; Conference date: 19-01-1988 Through 20-01-1988",

}

Felten, EW 1989, Best-first branch-And-bound on a hypercube. in G Fox (ed.), Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988. vol. 2, Association for Computing Machinery, Inc, pp. 1500-1504, 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988, Pasadena, United States, 1/19/88. https://doi.org/10.1145/63047.63107

TY - GEN

T1 - Best-first branch-And-bound on a hypercube

AU - Felten, Edward William

PY - 1989/1/3

Y1 - 1989/1/3

N2 - The branch-And-bound technique is a common method for finding exact solutions to difficult problems in combinatorial optimization. This paper will discusss issues surrounding implementation of a particular branch-And-bound algorithm for the traveling-salesman problem on a hypercube multicomputer. The natural parallel algorithm is based on a number of asynchronous processes which interact through a globally shared list of unfinished work. In a distributed-memory environment, we must find a non-centralized version of this shared data structure. In addition, detecting termination of the computation is tricky; an algorithm will be presented which ensures proper termination. Finally, issues affecting performance will be discussed.

AB - The branch-And-bound technique is a common method for finding exact solutions to difficult problems in combinatorial optimization. This paper will discusss issues surrounding implementation of a particular branch-And-bound algorithm for the traveling-salesman problem on a hypercube multicomputer. The natural parallel algorithm is based on a number of asynchronous processes which interact through a globally shared list of unfinished work. In a distributed-memory environment, we must find a non-centralized version of this shared data structure. In addition, detecting termination of the computation is tricky; an algorithm will be presented which ensures proper termination. Finally, issues affecting performance will be discussed.

UR - http://www.scopus.com/inward/record.url?scp=84869042921&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84869042921&partnerID=8YFLogxK

U2 - 10.1145/63047.63107

DO - 10.1145/63047.63107

M3 - Conference contribution

AN - SCOPUS:84869042921

VL - 2

SP - 1500

EP - 1504

BT - Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988

A2 - Fox, Geoffrey

PB - Association for Computing Machinery, Inc

T2 - 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988

Y2 - 19 January 1988 through 20 January 1988

ER -

Best-first branch-And-bound on a hypercube

Abstract

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this