Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Laurent Simon <>
Submitted on : Thursday, November 17, 2011 - 10:09:15 AM
Last modification on : Thursday, September 9, 2021 - 4:52:02 PM


  • HAL Id : hal-00642014, version 1



Laurent Simon, Chu Min Li, Felip Manya, Zhu Zhu. Minimum Satisfiability and its Applications. International Joint Conference on Artificial Intelligence, Jul 2011, Barcelona, Spain. ⟨hal-00642014⟩



Record views