Z3py SMT编码遵循变量和公式

Question

我对 Z3 和 SMT 求解器真的很陌生。我有以下问题，我不知道如何在 Z3py 中编码。

在上图中，N 是一组节点，因此 N = {Node1, Node2, Node3, Node4, Node5, Node6, Node7}

I 是一组输入，I = {I₁, I₂, I₃, 我₄}

O 是一组输出，O = {O₁, O₂, O₃}

G是一个组，其中对于任何连续的2个输出（O_i，O_j），如果O_i 是第一个生成的输出，O_j 是第二个生成的输出，G_k 是在O_i 的生成和 O_j 的生成之前，but if O_j 在 O_i 之前生成然后 G_k 包含在 O_{j[ 之前调度的所有块=183=] 已生成。
节点的调度由另一个程序给出。
例如，在上面的框图中，节点的调度以及输出的生成如下：}

计划的第一个节点 = Node1
计划的第二个节点 = Node2
计划的第三个节点 = Node5
生成的输出 = O₁
计划的第四个节点 = Node3
第五个节点预定 = Node6
生成的输出 = O₂
第六个节点预定 = Node4
第五个节点已安排 = Node7
生成的输出 = O₃

因此从上面我们可以说 G₁ for (O₁, O₂) = {Node3, Node6}

但是 G₂ 对于 (O₂, O₁) 是 = {Node1 , 节点 2, 节点 5}

要执行每个节点我们需要一个任务，一个任务一次可以执行一个节点或一组节点。

节点_r,i表示组G_r中的第i^个个节点。 Task_r,m表示组G_r.

中第m^th个任务

布尔变量（可以是 0 或 1）：

f_{Node_r,iTask_r,m}表示如果 Node_r,i映射到Task_r,m
DN_{Node_r,iNode_s,j}表示如果 Node_s,j 依赖于 Node_r,i 即如果有从 Node_{r,i[=183= 的路径]到节点_s,j}
DT_{Task_r,mTask_s,n}表示如果任务_s,n依赖于任务_r,m
M_{Task_r,m}表示是否有节点映射到Task_r,m

根据以上信息，我必须在 SMT 中制定以下等式。

最小化 ( Σ_r,m M_{任务_r,m})
M_{任务_r,m} >= f_{Node_r,iTask_r,m} (for all i)
Σ_m f_{Node_r,iTask_r,m} = 1（对于所有 r != I,O ) 示例： f_{Node_r,iTask_{r, m}} + f_{节点_r,i任务_r,m+1} + f_{节点_r,i任务_r,m+2} = 1 + 0 + 0 = 这告诉我们 Node_r,i 被映射到 Task_r,m 因为 f_{Node_r,iTask_r,m} = 1（一次只能将一个节点映射到1个任务，但一个任务可以映射到多个一个节点）
f_{Node_r,iTask_s,m} = 0（对于所有 r != s)
f_{Node_r,iTask_r,m} = 1（对于所有 r = I,O 和 m = i)
f_{Node_r,iTask_r,m} = 0（对于所有 r = I,O 和 m != i)
DT_{任务_r,m任务_s,n} >= f_{节点_r,i任务_r,m} + f_{节点_{s, j}任务_s,n} + DN_{节点_r,i节点_s,j} - 2
DT_{任务_r,m任务_s,n} >= DT_{任务_r,m任务_t,l} + DT_{任务_{t, l}任务_s,n} - 1
DT_{任务_r,m任务_s,n} + DT_{任务_s,n任务_r,m} <= 1

我不明白如何用 SMT 格式表示变量和这些公式。

Answer 1

我不确定如何最好地回答这个问题，因为该问题包含很多未完全指定的细节参考。例如，I 和 O 是什么？您可能会问如何添加线性不等式系统。或者如何指定可以为 0 或 1 的整数变量的问题。

一种方法是引入函数如下：

       a = Function('a', IntSort(), IntSort(), IntSort())

然后'a'是一个将整数对映射到整数的函数。您可以用类似的方式声明函数 'n' （但我猜您的示例实际上有一些拼写错误，并且您将 n 既用作函数又用作索引变量）。您也可以用类似的方式声明函数 f、h、q。

然后在python中可以这样写：

     N = 5
     s = Solver()  # create a solver context
     for r in range(N):
         for i in range(N):
             for m in range(N):
                 if m != i:
                     s.add(f(n(r,i),a(r,m)) == 0)

这会在您指定的 f 上添加等式约束。可以用类似的方式添加其他等式和不等式约束。最后你问结果状态是否可满足。

    print s.check()
    print s.model()   # print model for satisfiable outcome.

其他方法是为不同的对象声明不同的常量 f的版本。毕竟你建议的问题表明你只是写下一个由不同变量创建的不等式的大系统方式。

例如，您可以创建常量 v:

    v = Const('f(a[%d][%d],a[%d][%d])' % (r,m,r,i), IntSort())

而不是函数应用程序。

Z3py SMT编码遵循变量和公式

Z3py SMT coding following variables and the formulas

smt

z3

z3py