An Exact Inference Scheme for MinSAT

Li, Chu-Min; Manyà, Felip

An Exact Inference Scheme for MinSAT

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 1959-1964.

Abstract

We describe an exact inference-based algorithm for the MinSAT problem. Given a multiset of clauses Φ, the algorithm derives as many empty clauses as the maximum number of clauses that can be falsified in Φ by applying finitely many times an inference rule, and returns an optimal assignment. We prove the correctness of the algorithm, describe how it can be extended to deal with weighted MinSAT and weighted partial MinSAT instances, analyze the differences between the MaxSAT and MinSAT inference schemes, and define and empirically evaluate the MinSAT Pure Literal Rule.

Chu-Min Li, and Felip Manyà. 2015. An Exact Inference Scheme for MinSAT. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 1959–1964. https://ijcai.org/proceedings/2015/278

@inproceedings{ijcai2015p278,
  title     = {An Exact Inference Scheme for MinSAT},
  author    = {Li, Chu-Min and Manyà, Felip},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {1959--1964},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/278},
}

TY  - CPAPER
TI  - An Exact Inference Scheme for MinSAT
AU  - Li, Chu-Min
AU  - Manyà, Felip
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 1959
EP  - 1964
UR  - https://ijcai.org/proceedings/2015/278
ER  -