Z3 每次重新排序参数时都会给出不同的答案。优化问题

Question

每次我运行我的项目，都会生成不同顺序的 Z3 公式。即使公式完全相同，它在不同的运行中重新排序，结果，从 Z3 获得的答案在每个运行中都是不同的。这引起了问题，因为我需要一个最佳集，每个运行.

中应该完全相同

例如

第一个运行是：

(declare-const l1 (_ BitVec 1))
(declare-const l2 (_ BitVec 1))
(declare-const l3 (_ BitVec 1))
(declare-const l4 (_ BitVec 1))
(declare-const l5 (_ BitVec 1))
(declare-const l6 (_ BitVec 1))
(declare-const l7 (_ BitVec 1))
(declare-const l8 (_ BitVec 1))
(declare-const l9 (_ BitVec 1))
(declare-const l10 (_ BitVec 1))

(minimize (bvadd l1 l2 l3 l4 l5 l6 l7 l8 l9 l10))

(maximize 
    (bvand 
        (bvor (bvand l3 l4 l1 l2) (bvand l4 l2) (bvand l4 l1 l2) (bvand l2 l3 l4)) 

        (bvor (bvand l4 l2) (bvand l2 l3 l4)) 

        (bvor (bvand l5 l7 l8 l10 l6) (bvand l5 l7 l8 l6) (bvand l5 l7 l8 l9 l6) (bvand l5 l7 l8 l9 l10 l6) (bvand l5 l7 l6) (bvand l5 l7 l9 l10 l6) (bvand l5 l7 l10 l6))
    )
)
(check-sat)
(get-model)

给出了解决方案：l7, l5, l2, l4, l6, l8.
在这种情况下有 6 个是正确的。

第二个运行是：

(declare-const l1 (_ BitVec 1))
(declare-const l2 (_ BitVec 1))
(declare-const l3 (_ BitVec 1))
(declare-const l4 (_ BitVec 1))
(declare-const l5 (_ BitVec 1))
(declare-const l6 (_ BitVec 1))
(declare-const l7 (_ BitVec 1))
(declare-const l8 (_ BitVec 1))
(declare-const l9 (_ BitVec 1))
(declare-const l10 (_ BitVec 1))

(minimize (bvadd l1 l2 l3 l4 l5 l6 l7 l8 l9 l10))

(maximize 
    (bvand
        (bvor (bvand l2 l3 l4) (bvand l2 l4) (bvand l1 l2 l4) (bvand l2 l3 l4 l1)) 

        (bvor (bvand l2 l3 l4) (bvand l2 l4)) 

        (bvor (bvand l10 l6 l5 l7 l9) (bvand l10 l6 l5 l7) (bvand l10 l6 l5 l7 l8 l9) (bvand l10 l6 l5 l7 l8) (bvand l7 l6 l5) (bvand l7 l8 l9 l6 l5) (bvand l7 l8 l6 l5))
    )
)

(check-sat)
(get-model)

给出了解决方案：l7、l9、l5、l2、l4、l6、l8, l3.
在这种情况下有 8 个为真。

对于我的项目，我需要一个最优的、最小化的集合。根据之前解释的条件，我需要尽可能少的变量为真。对于这两个运行，正确的最佳答案应该是：l2、l4、l5、l6、l7 (5真的）。基本上我需要最小化成本并满足 maximize 条件内的条件。

但是，我没有给出 5 个变量为真的最优解，而是获得了 6、8、10 个真值。
我也尝试过用 (assert (= (bvand ...) #b1) ) 代替 (maximize (bvand ...) )，但无济于事。

如何获得最小、最佳数量的真实变量，这些变量也满足条件并且每次都给出相同的结果，即使在重新排序时也是如此？

注意：我不能使用 Int 或 Bool，因为我的程序可能会很大并且 int/bool 无法处理它。

Answer 1

这里有几个问题。首先，您使用 bvadd 来最小化和，它执行机器算术。也就是说，它将溢出位向量大小。（也就是说，该值始终为 0 或 1。）为避免这种情况，请在更大的位向量大小上进行加法运算：

(define-fun ext ((x (_ BitVec 1))) (_ BitVec 8)
    ((_ zero_extend 7) x))

(minimize (bvadd (ext l1) (ext l2) (ext l3) (ext l4) (ext l5) (ext l6) (ext l7) (ext l8) (ext l9) (ext l10)))

在这里，我在添加之前将值扩展为 8 位：由于您有 10 个变量，因此 8 位足以表示 10 的总数。（在这种情况下，您也可以使用 4 位；但这并不重要。只要确保它的宽度足以表示您要添加的变量总数即可。）

但是这里还有第二个问题。您要求 z3 首先最小化这个总和，然后最大化您的第二个表达式。 Z3 将进行词典优化，这意味着它将首先处理您的第一个约束，然后使用第二个约束。但是您的第一个将使所有变量 0 最小化总和。为避免这种情况，请确保交换约束的顺序。

作为最后的评论：你确实明确地说 "note: I cannot use Int or Bool since my programs are likely going to be huge and int/bool would be unable to handle it." 我觉得这很可疑。对于这样的问题，Bool 将是最明显和最佳的选择。特别是，优化器处理布尔值比处理位向量和整数要容易得多。所以，我建议不要在没有实际试验和没有证据证明它无法扩展的情况下放弃这个想法。

Z3 每次重新排序参数时都会给出不同的答案。优化问题

Z3 gives a different answer each time upon reordering parameters. Optimization problem

optimization

minimize

bitvector

z3

z3py

如何获得最小、最佳数量的真实变量，这些变量也满足条件并且每次都给出相同的结果，即使在重新排序时也是如此？