Minimum Satisfiability and Its Applications
Minimum Satisfiability and Its Applications
复制标题
DOI：
10.5591/978-1-57735-516-8/ijcai11-108
复制
发表时间：
2011-07
期刊：
影响因子：
--
通讯作者：
Chu Min Li;Zhu Zhu-Zhu;F. Manyà;Laurent Simon
中科院分区：
文献类型：
--
作者：
Chu Min Li;Zhu Zhu-Zhu;F. Manyà;Laurent Simon
我们定义的最小可满足性问题（MinSAT）的解决技术，提出了一个有效的分支定界算法来解决加权部分MinSAT问题，并报告的经验评估算法的Min-3SAT，最大集团，组合拍卖问题。求解MinSAT的技术与求解MaxSAT的技术有很大的不同。我们的研究结果提供了经验证据，通过将组合优化问题简化为MinSAT来解决组合优化问题可能比将其简化为MaxSAT要快得多，甚至可以与特定算法竞争。我们还使用MinSAT研究一个有趣的相关性之间的最小数量和最大数量的SAT实例满意的条款。
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, Max-Clique, 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.