A New Encoding from MinSAT into MaxSAT
A New Encoding from MinSAT into MaxSAT
复制标题
从 MinSAT 到 MaxSAT 的新编码
DOI：
10.1007/978-3-642-33558-7_34
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
J.Argelich
中科院分区：
文献类型：
--
作者：
Z.Zhu;C.M.Li;F.Manyà;J.Argelich
MinSAT问题是寻找一个真值赋值，使CNF公式中满足条件的子句的数量最小化。当我们区分硬子句和软子句，并且软子句具有相关联的权重时，则称为加权部分MinSAT的问题在于找到满足所有硬子句的真值分配，并且最小化满足的软子句的权重之和。本文定义了一种新的从加权部分最小可达到加权部分最大可达的编码方法，该方法同样适用于将加权部分最大可达编码为加权部分最小可达。此外，我们报告的实证调查表明，我们的编码显着优于现有的编码加权和未加权Min2SAT和Min3SAT的实例。
MinSAT is the problem of finding a truth assignment that minimizes the number of satisfied clauses in a CNF formula. When we distinguish between hard and soft clauses, and soft clauses have an associated weight, then the problem, called Weighted Partial MinSAT, consists in finding a truth assignment that satisfies all the hard clauses and minimizes the sum of weights of satisfied soft clauses. In this paper we define a novel encoding from Weighted Partial MinSAT into Weighted Partial MaxSAT, which is also valid for encoding Weighted Partial MaxSAT into Weighted Partial MinSAT. Moreover, we report on an empirical investigation that shows that our encoding significantly outperforms existing encodings on weighted and unweighted Min2SAT and Min3SAT instances.
登录
查看更多内容
影响因子：
1.6
作者：
Chu Min Li;F. Manyà;N. Mohamedou;Jordi Planes
通讯作者：
Chu Min Li;F. Manyà;N. Mohamedou;Jordi Planes
DOI：
10.1007/978-3-642-34413-8_40
发表时间：
2012-01
期刊：
--
影响因子：
--
作者：
Adrian Kügel
通讯作者：
Adrian Kügel
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
影响因子：
3.6
作者：
S. Vajda
通讯作者：
S. Vajda
DOI：
10.3233/978-1-58603-929-5-613
发表时间：
2009-01-01
期刊：
HANDBOOK OF SATISFIABILITY
影响因子：
--
作者：
Li, Chu Min;Manya, Felip
通讯作者：
Manya, Felip