On the Configuration of SAT Formulae

Mauro Vallati, Marco Maratea

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

It is well-known that the order in which clauses and literals are listed in a SAT formulae can have a strong impact on solvers’ performance. In this work we investigate how the performance of SAT solvers can be improved by a specifically-designed SAT formulae configuration. We introduce a fully automated approach for this configuration task, that considers a number of criteria for optimising the order in which clauses and, within clauses, literals, are listed in a formula expressed using the Conjunctive Normal Form. Our experimental analysis, involving three state-of-the-art SAT solvers and six different benchmark sets, shows that the configurations identified by the proposed approach can have a significant positive impact on solvers’ performance.
Original languageEnglish
Title of host publicationAI*IA 2019 – Advances in Artificial Intelligence
Subtitle of host publicationXVIIIth International Conference of the Italian Association for Artificial Intelligence, Rende, Italy, November 19–22, 2019, Proceedings
EditorsMario Alviano, Gianluigi Greco, Francesco Scarcello
Place of PublicationCham
PublisherSpringer Verlag
Pages264-277
Number of pages14
VolumeLNAI 11946
Edition1st
ISBN (Electronic)9783030351663
ISBN (Print)9783030351656
DOIs
Publication statusPublished - 17 Nov 2019
Event18th International Conference of the Italian Association for Artificial Intelligence - University of Calabria, Rende, Italy
Duration: 19 Nov 201922 Nov 2019
Conference number: 18
https://aiia2019.mat.unical.it/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Conference of the Italian Association for Artificial Intelligence
Abbreviated titleAIIA 2019
CountryItaly
CityRende
Period19/11/1922/11/19
Internet address

Cite this

Vallati, M., & Maratea, M. (2019). On the Configuration of SAT Formulae. In M. Alviano, G. Greco, & F. Scarcello (Eds.), AI*IA 2019 – Advances in Artificial Intelligence: XVIIIth International Conference of the Italian Association for Artificial Intelligence, Rende, Italy, November 19–22, 2019, Proceedings (1st ed., Vol. LNAI 11946, pp. 264-277). (Lecture Notes in Computer Science). Cham: Springer Verlag. https://doi.org/10.1007/978-3-030-35166-3_19