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
Go to the corresponding LIPIcs Volume Portal

Beldjilali, Abdelkader ; Montalbano, Pierre ; Allouche, David ; Katsirelos, George ; de Givry, Simon

Parallel Hybrid Best-First Search

LIPIcs-CP-2022-7.pdf (0.8 MB)


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

  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 =		{},
  URN =		{urn:nbn:de:0030-drops-166362},
  doi =		{10.4230/LIPIcs.CP.2022.7},
  annote =	{Keywords: Combinatorial Optimization, Parallel Branch-and-Bound, CFN}

Keywords: Combinatorial Optimization, Parallel Branch-and-Bound, CFN
Collection: 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
Issue Date: 2022
Date of publication: 23.07.2022
Supplementary Material: Software (Source Code): archived at:
Other (Results):

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI