Paper Info
Title
A General Purpose Branch and Bound Parallel Algorithm
Abstract
In this paper a parallel algorithm for branch and bound applications is proposed. The algorithm is a general purpose one and it can be used to parallelize effortlessly any sequential branch and bound style algorithm, that is written in a certain format. It is a distributed dynamic scheduling algorithm, i.e. each node schedules the load of its cores, it can be used with different programming platforms and architectures and is a hybrid algorithm (OpenMP, MPI). To prove its validity and efficiency the proposed algorithm has been implemented and tested with numerous examples in this paper that are described in detail. A speed-up of about 9 has been achieved for the tested examples, for a cluster of three nodes with four cores each.
Year
DOI
Venue
2016
10.1109/PDP.2016.33
2016 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP)
Keywords
Field
DocType
Branch and Bound,parallel algorithms,OpenMP,MPI,cluster
Analysis of parallel algorithms,Branch and bound,Hybrid algorithm,Parallel algorithm,Computer science,Parallel computing,Probabilistic analysis of algorithms,Schedule,Dynamic priority scheduling,Cluster analysis,Distributed computing
Conference
ISSN
Citations 
PageRank 
1066-6192
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Alexandros C. Dimopoulos1235.50
Christos Pavlatos2164.74
George K. Papakonstantinou315961.88