Minimum Satisfiability and Its Applications
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.
Cite
Text
Li et al. "Minimum Satisfiability and Its Applications." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-108Markdown
[Li et al. "Minimum Satisfiability and Its Applications." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/li2011ijcai-minimum/) doi:10.5591/978-1-57735-516-8/IJCAI11-108BibTeX
@inproceedings{li2011ijcai-minimum,
title = {{Minimum Satisfiability and Its Applications}},
author = {Li, Chu Min and Zhu, Zhu and Manyà, Felip and Simon, Laurent},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {605-610},
doi = {10.5591/978-1-57735-516-8/IJCAI11-108},
url = {https://mlanthology.org/ijcai/2011/li2011ijcai-minimum/}
}