从 ILP 到 SAT 的复试时间减少吗？

Question

因此，众所周知，ILP 的 0-1 决策问题是 NP 完全的。在 NP 中显示它很容易，并且最初的还原来自 SAT；从那时起，许多其他 NP 完全问题已被证明具有 ILP 公式（其功能是将这些问题简化为 ILP），因为 ILP 非常有用。

减少 从 ILP 似乎很难自己做或追踪。

因此，我的问题是，有谁知道从 ILP 到 SAT 的多时间减少，即演示如何使用 SAT 解决任何 0-1 ILP 决策问题？

Answer 1

0-1 ILP公式为：

是否存在vector $ mathbf {x} $，但要受到约束：

$ left。 ＆a_ {22} x_2＆... +＆a_ {2n} x_n le b_2 ... a_ {m1} x_1＆ +＆a_ {m2} x_2＆... le b_m end {array} right。 $$

x的域：$ forall_ {x_j in mathbf {x}} x_j in {0,1 } $

减少到K-Sat：

首先减少到SAT：

从第一行开始，创建一个布尔变量，用于表示$ a_ {1j} $中的每个位，而一个布尔值变量为$ x_j $。然后使$ b_1 $的变量变量。制作加法电路（选择您的喜欢），添加行。

然后进行比较电路，宣布总和小于$ b_1 $。

将这两个电路转换为CNF，填充$ a_ {1j} $变量和$ b_1 $，因此给出了$ b_1 $。

重复所有行，但重复使用它们之间的$ x_j $变量。

最终的CNF将包含所有约束。

Answer 2

这是对已经回答和接受的问题的某种死胡同，但我想指出，确实有更简单的方法。

考虑一下您有这样的不平等之一：

$5*x_1 + 2*x_2 + 3*x_3 \leq 6$

您可以轻松地测试所有无向量的不等式： $(1, 1, 1)$, $(1, 1, 0)$ 和 $(1, 0, 1)$ 其他都还好。

第一个向量 $(1, 1, 1)$ 意味着这三个不可能都为真： $ eg(x_1 \土地 x_2 \土地 x_3)$ 我们可以将其重写为析取 $( eg x_1 \lor eg x_2 \lor eg x_3)$.

这样你就可以从无向量形成 3 个子句： $( eg x_1 \lor eg x_2 \lor eg x_3)$, $(\负x_1\或\负x_2\或x_3)$ 和 $(\负x_1\或x_2\或\负x_3)$

遍历所有不等式并收集子句，最终将得到 cnf。通常这个 cnf 会更简单，然后是由接受的答案得出的结果。不过，预处理的成本更高。