编码一组最多的约束作为最大sat问题

Question

假设一组变量 $ v $ = $ \ {v_1，...，v_m \} $ < / span>。

给定总计 $ n $ 最多一个（amo）约束（在给定集中的大多数元素是 true ）设置[下面表格]，在变量集中 $ v $ ，

$$ amo \，（v_1，v4，\ neg v_6，v_ {10}）\\ ... \\ amo \，（v_2，\ neg v3，v_7 ）$$

Problem: Find an assignment to $V$ that maximize
         the number of satisfiable AMO constraint set. 

.

我无法将其代表为max-sat问题。

到目前为止尝试（尝试1）：为最多一个约束使用硬约束。这将无法作为 $ amo（v_i，...，v_w）$ 将为每个 $的子句amo $ 和所有这些都有相同的重量（顶部重量）。该组的解决方案可能不是最大的解决方案。

尝试（2）：解决上述问题，我尝试了相对条款重量;即，对于每个子句分配重量与子句的大小成比例。这将优先考虑令人满意的缩短条款。但如果所有条款都有相同的长度，这就不适用于极端情况。

我有SAT求解器的经验，但这是我的第一个MAX-SAT问题尝试。

Answer 1

在MaxSAT中创建软约束的标准方法是使用标签变量：

对于每个 $ amo_j $ 约束，创建一个新变量 $ l_j $ 。然后创建一个单位子句 $（\ lnot l_j）$ with权重 $ 1 $ 并添加文字 $ l_j $ 到标准的每个子句 $ amo_j $ 编码，该编码只包含硬（无限权重）子句。

现在标签变量 $ l_j $ 作为交换机，设置 $ l_j= true $ 将“关闭” $ amo_j $ 硬约束，但不满足单位子句 $（\ lnot l_j）$ 。