Minimum Satisfiability and Its Applications

Li, Chu-Min; Zhu, Zhu; Manyà, Felip; Simon, Laurent

doi:10.5591/978-1-57735-516-8/IJCAI11-108

Minimum Satisfiability and Its Applications

Chu Min Li, Zhu Zhu, Felip Manyà, Laurent Simon

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 605-609.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-108

Abstract

We define solving techniques for the Minimum Satisfiability Problem (MinSAT), propose an efficient branch-and-bound algorithm to solve the Weighted Partial MinSAT problem, and report on an empirical evaluation of the algorithm on Min-3SAT, MaxClique, and combinatorial auction problems. Techniques solving MinSAT are substantially different from those for the Maximum Satisfiability Problem (MaxSAT). Our results provide empirical evidence that solving combinatorial optimization problems by reducing them to MinSAT may be substantially faster than reducing them to MaxSAT, and even competitive with specific algorithms. We also use MinSAT to study an interesting correlation between the minimum number and the maximum number of satisfied clauses of a SAT instance.

Chu-Min Li, Zhu Zhu, Felip Manyà, and Laurent Simon. 2011. Minimum Satisfiability and Its Applications. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 605–609. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-108

@inproceedings{ijcai2011p108,
  title     = {Minimum Satisfiability and Its Applications},
  author    = {Li, Chu-Min and Zhu, Zhu and Manyà, Felip and Simon, Laurent},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {605--609},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-108},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-108},
}

TY  - CPAPER
TI  - Minimum Satisfiability and Its Applications
AU  - Li, Chu-Min
AU  - Zhu, Zhu
AU  - Manyà, Felip
AU  - Simon, Laurent
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 605
EP  - 609
DO  - 10.5591/978-1-57735-516-8/IJCAI11-108
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-108
ER  -