SAT 求解器和相位节省
SAT Solvers and Phase Saving
DPLL SAT solvers typically apply a Phase Saving 启发式。这个想法是记住每个变量的最后一次分配并在分支中使用它 first 。
为了试验分支极性和相位节省的效果，我尝试了几个 SAT 求解器并修改了相位设置。都是Windows 64位端口，运行单线程模式。我总是使用中等复杂度的相同示例输入（5619 个变量，11261 个子句，在解决方案中所有变量的 4% 为真，96% 为假）。
结果 运行 次如下所列：
这可能只是（坏）运气，但差异非常大。令人特别惊讶的是，对于我的示例，MiniSat 的性能优于所有现代求解器。
我的问题：
Are there any explanations for the differences?
Best practices for polarity and phase saving?
无法从您的测试中得出任何结论。众所周知，DPLL 和基于它的求解器会根据初始搜索条件表现出重尾行为。这意味着同一求解器可以在同一实例上同时具有短期和长期运行时间，具体取决于随机重启发生的时间等因素。不同求解器的搜索时间可能会根据（例如）它们如何选择决策变量而有很大差异，即使没有阶段保存和随机重启的额外复杂性。
DPLL SAT solvers typically apply a Phase Saving 启发式。这个想法是记住每个变量的最后一次分配并在分支中使用它 first 。
为了试验分支极性和相位节省的效果，我尝试了几个 SAT 求解器并修改了相位设置。都是Windows 64位端口，运行单线程模式。我总是使用中等复杂度的相同示例输入（5619 个变量，11261 个子句，在解决方案中所有变量的 4% 为真，96% 为假）。
结果 运行 次如下所列：
这可能只是（坏）运气，但差异非常大。令人特别惊讶的是，对于我的示例，MiniSat 的性能优于所有现代求解器。
我的问题：
Are there any explanations for the differences?
Best practices for polarity and phase saving?
无法从您的测试中得出任何结论。众所周知，DPLL 和基于它的求解器会根据初始搜索条件表现出重尾行为。这意味着同一求解器可以在同一实例上同时具有短期和长期运行时间，具体取决于随机重启发生的时间等因素。不同求解器的搜索时间可能会根据（例如）它们如何选择决策变量而有很大差异，即使没有阶段保存和随机重启的额外复杂性。