z3py 中的 Optimize() 未找到最佳解决方案

Question

我正在尝试使用 z3py 作为优化求解器来最大化从一张纸上剪下的长方体的体积。 python API 提供了 Optimize() 对象，但使用它似乎不可靠，给我的解决方案显然不准确。

我试过使用 h = opt.maximise 然后 opt.upper(h) 以及简单地检查模型，以及在将长方体添加到模型之前定义长方体的体积 v = w*b*l以及之后，以及将 objective 设置为 w*b*l 而不是 v。 None 他们给了我任何类似好的解决方案。

from z3 import *
l = Real("l")
w = Real("w")
b = Real("b")
v = Real("v")
opt = Optimize()
width = 63.6
height = 51

opt.add(b+l <= width)
opt.add(w+b+w+l+w <= height)
opt.add(w > 0)
opt.add(b > 0)
opt.add(l > 0)
opt.add(v == w*b*l)
opt.maximize(w * b * l)
# h = opt.maximize(v)


print(opt.check())
# print(opt.upper(h))
print(opt.model())

输出：

unknown
[w = 1, b = 1, l = 47, v = 47]

这绝对不是最大值。将所有值设置为 10 可提供满足约束条件的更好的解决方案。

Answer 1

Z3 的优化器无法处理 non-linear 问题。事实上，这正是它打印 unknown 的原因。当你看到对 check returning unknown 的调用时，它恰恰意味着：Z3 不知道问题是否可满足，更不用说它是否找到了最优解。

如果您添加：

print(opt.reason_unknown())

调用 check 后，您将看到：

(incomplete (theory arithmetic))

在这些情况下，对 model 的调用将 return 在解决问题时获得一些中间结果 z3，但决不能保证它是最佳的。

你的问题是 non-linear 因为你在乘以变量。（w、b 和 l。）Z3 可以解决实数上的非线性可满足性问题，但不能[=36] =] 优化问题。例如，参见此处：z3Opt optimize non-linear function using qfnra-nlsat

（请注意，与纯粹的可满足性相比，非线性优化对于实数来说是一个更难的问题。因此，这不仅仅是 "not having implemented it yet." 的问题）

z3py 中的 Optimize() 未找到最佳解决方案

Optimize() in z3py not finding optimal solutions

optimization

mathematical-optimization

z3

z3py