z3 的可扩展性

Yua*_*hou 3 z3 z3py

我想提高 SMT 求解的可扩展性。我实际上已经实现了增量求解。但我想提高更多。在不了解问题本身的情况下,还有其他一般方法可以改进它吗?

ali*_*ias 6

没有单一的“技巧”可以使 z3 更好地解决任意问题。这实际上取决于实际问题是什么以及您有什么样的限制。当然,这适用于任何一般计算问题,但它确实适用于 SMT 求解器的上下文。

话虽如此,这里有一些基于我的经验的一般想法,大致按照易用性的顺序:

阅读Programming Z3本书这是一篇非常好的文章,将教您大量有关 z3 的架构以及最佳习语的知识。您可能会遇到直接适用于您的问题的内容:https : //theory.stanford.edu/~nikolaj/programmingz3.html

保持布尔值作为布尔值而不是整数永远不要使用整数来表示布尔值。(也就是说,1用于真、0假;乘法and等。这是一个可怕的想法,它会杀死下面强大的 SAT 引擎。)如有必要,显式转换。人们倾向于使用此类技巧的大多数问题都涉及计算有多少布尔值为真等:此类问题应该使用求解器内置的伪布尔策略来解决。(查找pbEqpbLt等等)

除非绝对必要否则不要优化优化引擎不是增量的,也不是很好的优化(双关语)。与所有其他引擎相比,它的工作速度相当慢,这是有充分理由的:优化模理论是一件非常棘手的事情。除非您真的有优化问题需要解决,否则请避免使用它。您还可以尝试在求解器的“外部”进行优化:拨打SAT电话,获取结果,然后进行后续调用,要求“更小”的成本值。使用此技巧您可能无法达到最佳值,但经过几次迭代后,这些值可能已经足够好了。当然,结果的好坏完全取决于您的问题。

案例拆分尝试通过对关键变量进行案例拆分来减少约束。示例:如果您正在处理浮点约束,请说;分别对正常、非正常、无穷大和 NaN 值进行大小写拆分。根据您的特定领域,您可能有这样的语义类别,其中底层算法采用不同的路径,混合和匹配它们总是会给求解器带来困难。基于上下文的案例拆分可以加快速度。

使用更快的机器和更多的内存这是不言而喻的;但是拥有足够的内存确实可以加快某些问题的速度,尤其是当您有很多变量时。获得最大的机器!

充分利用您的内核您可能拥有一台具有多个内核的机器,而且您的操作系统很可能提供细粒度的多任务处理。利用这一点:启动 z3 的许多实例来解决相同的问题,但使用不同的策略、随机种子等;并取第一个完成的结果。如果您有一个巨大的约束集,随机种子可以发挥重要作用,因此运行更多具有不同种子值的实例可以让您平均“幸运”。

尝试使用并行求解大多数 SAT/SMT 求解器算法本质上都是顺序的。已经有许多关于如何并行化某些算法的论文,但大多数引擎没有并行对应物。z3 有一个用于并行求解的接口,尽管它的广告较少且相当挑剔。试一试,看看它是否有帮助。详细信息在这里:https : //theory.stanford.edu/~nikolaj/programmingz3.html#sec-parallel-z3

分析z3 源代码本身,因为它针对您的问题运行,并查看热点在哪里。看看您是否可以向开发人员推荐代码改进来解决这些问题。(更好的是,提交拉取请求!)不用说,这需要对 z3 本身进行深入研究,可能不适合最终用户。

一句话:天下没有免费的午餐。没有一种方法可以让 z3 更好地解决您的问题。但上述想法可能有助于改善运行时间。如果您详细描述了您正在处理的特定问题,您很可能会得到更好的建议,因为它适用于您的约束。