如何使用 Picat 从 Minizinc 文件创建 CNF 文件？

Question

我有兴趣计算一个问题的解决方案数量（不是列举解决方案）。为此，我有使用 CNF files. I want to convert Minizinc 文件（mzn 或 Flatzinc fzn 格式）并将其转换为 CNF 的工具。

我学会了 fzn_picat_sat.pi 的 Picat has the ability to "dump" a CNF file after loading the constraints. Moreover, Picat has a clever Module that interprets basic Flatzinc files. I modified the module fzn_picat_sat.pi to "dump" the CNF file. So, what I do is that I convert a Minizinc file to Flatzinc using mzn2fzn, then I try to convert it to CNF using my (slightly) modified version。

我想要什么：我希望 Picat 加载 Flatzinc 文件并转储适当的 CNF 文件。如果原题有X个解法，我希望对应的CNF有X个解法

发生了什么：我试过的大多数 Flatzinc 文件都运行良好。但是有些似乎会产生不需要的结果。例如，the following mzn translate to this Flatzinc file. That file has only 211 solutions, but the CNF file dumped by Picat has over 130k solutions. Many SAT solvers can show that the CNF file has over 211 solutions (for example cryptominisat 带有选项 --maxsol）。奇怪的是，当我要求 Picat 在不转换为 CNF 的情况下求解 Flatzinc 文件时，Picat 确实只找到了 211 个解。问题似乎出在翻译的某个地方。最后，即使 CNF 文件中有大量使用 Picat 的解决方案，我也会收到错误 % fzn_interpretation_error.

如果有人尝试过类似的事情并成功了，或者如果有人知道如何将 CP（约束编程）语言转换为 CNF，那将不胜感激。谢谢大家。

Answer 1

正如 Axel Kemper 在评论中提到的，MiniZinc 可能会添加不应用于区分多个解决方案的其他变量。作为一个简单的例子，考虑以下（人工）MiniZinc 模型

predicate separated(var int: x, var int: y) = 
    let {
      var int: z
    } in
     x < z /\ z < y;
     
var 1..10: x;
var 1..10: y;

constraint separated(x, y);

solve satisfy;

这里的谓词separated增加了另一个变量，只是用来证明x和y之间有一些数字（谓词等同于abs(x-y)>0）。

该模型有 36 个解（1,3、1,4、...、8,10）。但是，如果您考虑解决方案 3,8，则有 5 种不同的 z 选择使谓词为真。通常，用户很可能只对输出变量不同的解决方案感兴趣。

将上述 MiniZinc 转换为 CNF 时，谓词内部 z-variable 将不会与“真实”问题变量 x 和 y 区分开来。为了计算解决方案，您需要区分与模型中输出变量域对应的文字，并指示 SAT 求解器仅在这些文字不同时才考虑两个不同的解决方案（不确定这是否是一个特征可用）。

如何使用 Picat 从 Minizinc 文件创建 CNF 文件？

How to use Picat to create CNF files from Minizinc files?

constraint-programming

minizinc

sat

picat