Rodrigue Konan Tchinda ; Clémentin Tayou Djamegni - Parallel Hybridization for SAT: An Efficient Combination of Search Space Splitting and Portfolio

arima:6750 - Revue Africaine de Recherche en Informatique et Mathématiques Appliquées, February 27, 2021, Volume 34 - 2020 - Special Issue CARI 2020 - https://doi.org/10.46298/arima.6750
Parallel Hybridization for SAT: An Efficient Combination of Search Space Splitting and Portfolio

Authors: Rodrigue Konan Tchinda 1; Clémentin Tayou Djamegni 1

  • 1 Université de Dschang

Search space splitting and portfolio are the two main approaches used in parallel SAT solving. Each of them has its strengths but also, its weaknesses. Decomposition in search space splitting can help improve speedup on satisfiable instances while competition in portfolio increases robustness. Many parallel hybrid approaches have been proposed in the literature but most of them still cope with load balancing issues that are the cause of a non-negligible overhead. In this paper, we describe a new parallel hybridization scheme based on both search space splitting and portfolio that does not require the use of load balancing mechanisms (such as dynamic work stealing).


Volume: Volume 34 - 2020 - Special Issue CARI 2020
Published on: February 27, 2021
Accepted on: January 15, 2021
Submitted on: September 1, 2020
Keywords: SAT,portfolio,search space splitting,parallel hybridization,SAT,portfolio,DPR,hybridation parallèle,[INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1007/bfb0017434
Source : ScholeXplorer IsRelatedTo HANDLE 10400.5/27732
  • 10.1007/bfb0017434
  • 10400.5/27732
Heavy-tailed distributions in combinatorial search

Consultation statistics

This page has been seen 308 times.
This article's PDF has been downloaded 211 times.