解决SAT Solver解决这个子集问题是可行的吗？

Question

问题是找到 $ \ mathcal {s} $ ，最小收集 $ \ {1的子集，\ dots，17 \} $ 使得满足两个条件：

1. 如果 $ s \ supereteq \ mathcal {s} $ 那么 $ | s |= 6 $ ;
2. 对于任何 $ a \ subseteq \ {1，\ dots，17 \} $ with $ | a |= 3 $ ，存在 $ s \ in \ mathcal {s} $ 使用 $ a \ subset s $ 。

看这里用于相关组合问题..

我认为这可以制定为min sat问题。

对于每个 $ s \ subseteq \ {1，\ dots，17 \} $ 使用 $ | s |= 6 $ ，我们介绍了一个变量 $ x_s $ 。对于每个 $ a \ subseteq \ {1，\ dots，17 \} $ with $ | a |= 3 $ ，我们介绍一个条款 $$ \ vee_ {s：a \ subseteq s，| s |= 6} x_ {s} $$ 然后，在主体中，我们可以使用SAT Solver来查找最小数量的 $ x_s $ ，它需要真实来满足所有条款。

此需要 $ \ binom {17} {6}= 12376 $ 变量， $ \ binom {17} { 3}= 680 $ 长度 $ \ binom {17-3} {3}= 364 $ 。

我在实际使用SAT求解器中的经验很少。这实际上值得在我的笔记本电脑上尝试，或者根本没有希望？

--- ---

更新

结果有很多关于套装的研究。似乎我越来越雄心勃勃地尝试解决参数的问题（17,6,3）。

它已经是（12,5,3）的打开问题。

请参阅在这里更多详细信息。

--- ---

更新2

试图在纯粹的sat中写一切，它比z3使用cadical非常好。

此外，找到一个解决方案明显更快，而不是显示不存在的解决方案。

我试图通过添加必须选择词汇顺序中的第一个和最后一个子集的约束来打破对称性。

Answer 1

SAT的优化通常称为MaxSAT而不是Min Sat。特别是，我建议寻找“加权部分maxsat”的求解器，例如maxhs和rc2。

您在现代Maxsat-Solvers的背景下，您的问题大小相当小，所以是的，值得尝试。没有保证求解器将有效地工作，并且很难预测它是否会有效地工作，所以最好的事情就是尝试。

Answer 2

与sat，预测会挑战是有挑战性，什么是可行的，什么是不可行的。值得一试。

我建议，而不是minsat，你首先尝试在 $ n= | \ mathcal {s} | $ ，设置你的数量需要。您可以使用最多 - $ n $ -out-12376在 $ x_s $ 变量。有多个 技术 在sat中，虽然在练习中，我将首先尝试使用用z3求解器。

你的问题有很多对称性。 SAT溶剂有时会遇到对称性。您可能会尽可能多地进行打破对称性。例如，不损失普遍性，我们可以假设 $ \ {1,2,3,4,5,6 \} $ 是其中一个（否则置换所有数字所以它是），所以你可能会把这个事实困惑到你的SAT实例中。您可以证明的诸如此类lemmas越多，SAT Solver可能会表现越好。

您还可以以不同的方式对集合进行编码。让 $ s_i $ 表示 $ i $ $ \ mathcal {s} $ 。介绍variabless $ x_ {i，j} $ 指示 $ j \ in s_i $ 和变量<跨越类=“math-container”> $ y_ {i，a} $ 表示 $ a \ subset s_i $ ，每个 $ a \ subseteq \ {1，\ dots，17 \} $ 使用 $ | a |= 3 $ 和每个 $ i \ in \ {1，\ dots，n \} $ 和每个 $ j \ in \ {1， \ dots，17 \} $ 。添加子句 $ \ bigvee_i y_ {i，a} $ 为每个 $ a $ 以确保每个 $ a $ 由至少一个设置覆盖。为每个 $ i $ 为添加一个6-超出17个约束，以指示 $ x_ {i ，j} $ 是真的。最后，添加约束以在 $ x $ s和 $ y $ 的状态之间。特别是，对于每个 $ a={a_1，a_2，a_3 \} $ ，添加条文 $ \ neg x_ {我，a_1} \ lor \ neg x_ {i，a_2} \ lor \ neg x__ {i，a _3} \ lor y_ {i，a} $ 和 $ \ neg y_ {i，a} \ lor x_ {i，a_1} $ 和 $ \ neg y_ {i，a} \ lor x_ {i，a_2} $ < / span>和 $ \ neg y_ {i，a} \ lor x_ {i，a_3} $ 。这将需要关于 $（17 + 680）n $ 变量和 $ 4 \ cdot 680 n $ 条文（不计算 $ n $ 6-Out-17个约束）;由于我期待 $ n \大约35 $ ，这是大约24k变量和100k子句。这比你的编码更有条款，它有更多的对称性，所以它可能表现更糟 - 虽然他们是短的条款，但很难预测哪些编码将最能使用SAT，因此需要一些实验。

您还可以尝试将此作为ILP实例而不是SAT。