2026-07-21T14:16:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16636 2024-03-06T10:57:55Z ddc:004 open_access

Parallel Hybrid Best-First Search Beldjilali, Abdelkader Montalbano, Pierre Allouche, David Katsirelos, George de Givry, Simon Combinatorial Optimization Parallel Branch-and-Bound CFN 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Abdelkader Beldjilali and Pierre Montalbano and David Allouche and George Katsirelos and Simon de Givry 2022 Is Part Of LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2022.7 urn:nbn:de:0030-drops-166362 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.7 eng https://creativecommons.org/licenses/by/4.0/legalcode