在 z3py 中找到给定约束的变量的最大值

Question

例如，给定以下 4 个约束，a 和 x 是 ints，b 是 array，映射 int至 int：

a >= 0
b[0] == 10
x == 0
b[x] >= a

find_max(a) => 10
find_min(a) => 0

z3py 可以做这样的事情吗？

Answer 1

是的，当然。

您可以通过多个 single-objective 优化搜索逐步进行，或者使用更高效的 boxed (a.k.a。 Multi-Independent) z3 提供的组合，用于处理 multi-objective 优化。

Definition 4.6.3. (Multiple-Independent OMT [LAK+14, BP14, BPF15, ST15b, ST15c]). Let <φ,O> be a multi-objective OMT problem, where φ is a ground SMT formula and O = {obj_1 , ..., obj_N}, is a sorted list of N objective functions. We call Multiple-Independent OMT problem, a.k.a Boxed OMT problem [BP14, BPF15], the problem of finding in one single run a set of models {M_1, ...,M_N} such that each M_i makes obj_i minimum on the common formula φ.

Remark 4.6.3. Solving a Multiple-Independent OMT problem <φ, {obj_1, ..., obj_N }> is akin to independently solving N single-objective OMT problems <φ, obj_1>, ..., <φ, obj_N>. However, the former allows for factorizing the search and thus obtaining a significant performance boost when compared to the latter approach [LAK+14, BP14, ST15c].

[source, pag. 104]

示例：

from z3 import *

a = Int('a')
x = Int('x')
b = Array('I', IntSort(), IntSort())

opt = Optimize()

opt.add(a >= 0)
opt.add(x == 0)
opt.add(Select(b, 0) == 10)
opt.add(Select(b, x) >= a)

obj1 = opt.maximize(a)
obj2 = opt.minimize(a)

opt.set('priority', 'box')   # Setting Boxed Multi-Objective Optimization

is_sat = opt.check()
assert is_sat

print("Max(a): " + str(obj1.value()))
print("Min(a): " + str(obj2.value()))

输出：

~$ python test.py 
Max(a): 10
Min(a): 0

查看有关该主题的出版物，例如

1. Nikolaj Bjorner 和 Anh-Dung Phan. νZ - Z3 的最大满意度。 在 Proc 国际软件科学符号计算研讨会上，Gammart，突尼斯，2014 年 12 月。EasyChair 计算会议论文集 (EPiC)。 [PDF]

2. Nikolaj Bjorner、Anh-Dung Phan 和 Lars Fleckenstein。 Z3 - 优化SMT 求解器。 在 Proc。 TACAS，LNCS 第 9035 卷。施普林格，2015 年。[Springer] [[PDF]

在 z3py 中找到给定约束的变量的最大值

Find maximum value of a variable given constraints in z3py

python

z3

z3py