Cube-and-Conquer for Satisfiability
- Submitting institution
-
Swansea University / Prifysgol Abertawe
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 36186
- Type
- C - Chapter in book
- DOI
-
10.1007/978-3-319-63516-3_2
- Book title
- Handbook of Parallel Constraint Reasoning
- Publisher
- Springer
- ISBN
- 978-3-319-63515-6
- Open access status
- Out of scope for open access requirements
- Month of publication
- April
- Year of publication
- 2018
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
-
- Research group(s)
-
-
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This article describes the Cube-and-Conquer (C&C ) method, as developed by the three authors. Kullmann, joined by Heule, discovered the original method and applied it to Automated Theorem Proving. Biere adapted and implemented the method for industrial problems. Combining the older and new approach to Satisfiability Solving, yields the potential of being (1) faster than each individual method by orders of magnitudes, (2) highly parallelisable.
For hard combinatorial problems, C&C has become the standard for applications of Satisfiability. The industrial field is more diverse, but the solvers provided by Biere have been very competitive in the annual SAT Competitions.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -