Quantified maximum satisfiability: a core-guided approach

Alexey Ignatiev, Mikoláš Janota, Joao Marques-Silva

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

11 Citations (Scopus)

Abstract

In recent years, there have been significant improvements in algorithms both for Quantified Boolean Formulas (QBF) and for Maximum Satisfiability (MaxSAT). This paper studies the problem of solving quantified formulas subject to a cost function, and considers the problem in a quantified MaxSAT setting. Two approaches are investigated. One is based on relaxing the soft clauses and performing a linear search on the cost function. The other approach, which is the main contribution of the paper, is inspired by recent work on MaxSAT, and exploits the iterative identification of unsatisfiable cores. The paper investigates the application of these approaches to the concrete problem of computing smallest minimal unsatisfiable subformulas (SMUS), a decision version of which is a well-known problem in the second level of the polynomial hierarchy. Experimental results, obtained on representative problem instances, indicate that the core-guided approach for the SMUS problem outperforms the use of linear search over the values of the cost function. More significantly, the core-guided approach also outperforms the state-of-the-art SMUS extractor Digger.

Original languageEnglish
Title of host publicationTheory and Applications of Satisfiability Testing, SAT 2013 - 16th International Conference, Proceedings
PublisherSpringer
Pages250-266
Number of pages17
Volume7962
ISBN (Print)9783642390708
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event16th International Conference on Theory and Applications of Satisfiability Testing, SAT 2013 - Helsinki, Finland
Duration: 8 Jul 201312 Jul 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7962 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference on Theory and Applications of Satisfiability Testing, SAT 2013
CountryFinland
CityHelsinki
Period8/07/1312/07/13

Cite this

Ignatiev, A., Janota, M., & Marques-Silva, J. (2013). Quantified maximum satisfiability: a core-guided approach. In Theory and Applications of Satisfiability Testing, SAT 2013 - 16th International Conference, Proceedings (Vol. 7962, pp. 250-266). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7962 LNCS). Springer. https://doi.org/10.1007/978-3-642-39071-5_19