License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2022.7
URN: urn:nbn:de:0030-drops-166362
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16636/
Beldjilali, Abdelkader ;
Montalbano, Pierre ;
Allouche, David ;
Katsirelos, George ;
de Givry, Simon
Parallel Hybrid Best-First Search
Abstract
While processor frequency has stagnated over the past two decades, the number of available cores in servers or clusters is still growing, offering the opportunity for significant speed-up in combinatorial optimization. Parallelization of exact methods remains a difficult challenge. We revisit the concept of parallel Branch-and-Bound in the framework of Cost Function Networks. We show how to adapt the anytime Hybrid Best-First Search algorithm in a Master-Worker protocol. The resulting parallel algorithm achieves good load-balancing without introducing new parameters to be tuned as is the case, for example, in Embarrassingly Parallel Search (EPS). It has also a small overhead due to its light communication messages. We performed an experimental evaluation on several benchmarks, comparing our parallel algorithm to its sequential version. We observed linear speed-up in some cases. Our approach compared favourably to the EPS approach and also to a state-of-the-art parallel exact integer programming solver.
BibTeX - Entry
@InProceedings{beldjilali_et_al:LIPIcs.CP.2022.7,
author = {Beldjilali, Abdelkader and Montalbano, Pierre and Allouche, David and Katsirelos, George and de Givry, Simon},
title = {{Parallel Hybrid Best-First Search}},
booktitle = {28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
pages = {7:1--7:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-240-2},
ISSN = {1868-8969},
year = {2022},
volume = {235},
editor = {Solnon, Christine},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16636},
URN = {urn:nbn:de:0030-drops-166362},
doi = {10.4230/LIPIcs.CP.2022.7},
annote = {Keywords: Combinatorial Optimization, Parallel Branch-and-Bound, CFN}
}
