Z3 优化超时

Question

如何为 z3 优化器设置超时，以便在超时时为您提供最知名的解决方案？

from z3 import *
s = Optimize()
# Hard Problem
print(s.check())
print(s.model())

后续问题，z3可以设置为随机爬山还是一直执行完整搜索？

Answer 1

长话短说，你不能。这根本不是优化器的工作方式。也就是说，它没有找到解决方案然后尝试改进它。如果您中断它或设置超时，当计时器到期时，它甚至可能没有令人满意的解决方案，更不用说 "improved" 了。详情请看优化论文：https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/nbjorner-nuz.pdf

但是，z3 确实会跟踪变量的边界，以获取数值。您可能能够提取这些值，但一般来说，您无法知道您需要从这些间隔中选择哪些值才能为整个问题获得令人满意的解决方案。请参阅此答案进行讨论：

这类 "hill-climbing" 问题经常出现在这个论坛中。答案很简单，z3 的优化器不是这样工作的。以这种方式进行的一些先前问题：

z3 minimization and timeout

stack-overflow 中几乎没有其他类似的问题。搜索 "optimize" 和 "timeout".

你最好的选择

这就是它的理论方面。实际上，我认为处理此类问题的最佳方法是根本不使用优化器。而是执行以下操作：

说出你的问题
求模型。如果没有模型，请回复 unsat。退出。
保持当前模型为"best-so-far"
没时间了？ Return 您拥有的模型 "best-so-far"。你完成了。
还有时间吗？

5a。计算此模型的 "cost"。即，您尝试最小化或最大化的指标。如果您将成本作为变量存储在模型中，您可以简单地从模型中查询它的值。

5b。断言一个新的约束，说明成本应该低于当前模型的成本。（如果你正在最大化，则更高。）根据你想要的花哨程度，你可能想要 "double" 成本函数，或实施某种二进制搜索以更快地收敛到一个值。但这一切都取决于问题的具体细节。

5c。求新型号。如果 unsat，return 你得到的最后一个模型是 "optimal." 否则，从步骤 3 开始重复。

我相信这是 z3 中时间约束优化最实用的方法。它使您可以完全控制迭代次数，并以您想要的任何方式引导搜索。（例如，您可以在每个模型中查询各种变量，并通过说“给我找一个更大的 x 或更小的 y 等来指导搜索，而不是只看一个指标.) 希望这是有道理的。

总结

请注意，SMT 求解器可以像您描述的那样工作，即，在超时结束时为您提供目前为止最佳的解决方案。只是 z3 的优化器不是那样工作的。对于 z3，我发现上面描述的迭代循环是这种基于超时的优化最实用的解决方案。

您还可以查看 OptiMathSAT (http://optimathsat.disi.unitn.it/)，它可能在这方面提供更好的设施。 @Patrick Trentin 经常阅读这个论坛，是这方面的专家，他可能会就它的用法单独发表意见。

Answer 2

一般来说，@alias 是正确的，他说 OMT 求解器在优化搜索结束时不提供任何解决方案可用的保证，当优化搜索被 timeout 打断时信号。

OMT 求解器可以通过以下两种方式之一寻找最优解：

通过从公式的初始模型开始，并尝试改进objective函数的值；这是标准的 OMT 方法的情况，它枚举了许多部分优化的解决方案，直到找到最佳解决方案。
从超过最优的、不可满足的分配开始，逐步放松这种分配，直到产生最优解； AFAIK，这只是用于处理 MaxSMT 问题的 Maximum Resolution 引擎的情况。

当 OMT 求解器使用属于第一类的优化技术时，如果 OMT 求解器在运行期间将其存储在安全位置，则可以在时间用完时检索最知名的解决方案优化搜索。第二个 MaxRes 引擎不是这种情况（参见）。

可能的解决方法。 （注意：我还没有测试过） z3 跟踪优化搜索中 objective 函数的 lower 和 upper 边界。最小化时，upper 边界对应于 OMT 求解器找到的最近部分解中 objective 函数的值（对偶最大化）。在最小化（resp。最大化）从 minimize()（resp。maximize()）获得的 obj 实例时发生超时信号后，应该能够检索最新的近似值 v通过调用 obj.upper()（resp. obj.lower()）得到 obj 的最优值。假设这样的值 v 不同于 +oo（resp. -oo），我们可以逐步学习 cost = v 形式的约束并执行增量 SMT 检查可满足性重建对应于 z3.

的次优解的模型

OptiMathSAT 是一种 OMT 求解器，可将其在优化搜索期间遇到的最新解存储在安全位置。这样可以很容易地实现你想做的事情。

OptiMathSAT中有两种timeout信号：

硬超时：一旦timeout触发，优化搜索立即停止；如果 OMT 求解器找到任何解，则优化搜索的结果（可通过 msat_objective_result(env, obj) 访问）为 MSAT_OPT_SAT_PARTIAL 并且可以提取并打印对应于最新次优解的模型；相反，如果 OMT 求解器没有找到任何解，则优化搜索的结果是 MSAT_UNKNOWN 并且没有可用的模型。
软超时：如果在 OMT 求解器找到任何解后触发 timeout，则搜索将立即停止，如硬超时。否则，timeout 将被忽略，直到 OMT 求解器找到 one 解。

timeout信号的类型可以使用选项opt.soft_timeout=[true|false]设置。

示例： 以下示例是 timeout.py unit-test contained in my omt_python_examples github 存储库，其中包含许多如何使用 Python API OptiMathSAT.

接口

"""
timeout unit-test.
"""

###
### SETUP PATHS
###

import os
import sys

BASE_DIR = os.path.dirname(os.path.abspath(__file__))
INCLUDE_DIR = os.path.join(BASE_DIR, '..', 'include')
LIB_DIR = os.path.join(BASE_DIR, '..', 'lib')
sys.path.append(INCLUDE_DIR)
sys.path.append(LIB_DIR)

from wrapper import * # pylint: disable=unused-wildcard-import,wildcard-import

###
### DATA
###

OPTIONS = {
    "model_generation" : "true",      # !IMPORTANT!
    "opt.soft_timeout" : "false",
    "opt.verbose"      : "true",
}

###
### TIMEOUT UNIT-TEST
###

with create_config(OPTIONS) as cfg:
    with create_env(cfg) as env:

        # Load Hard Problem from file
        with open(os.path.join(BASE_DIR, 'smt2', 'bacp-19.smt2'), 'r') as f:
            TERM = msat_from_smtlib2(env, f.read())
            assert not MSAT_ERROR_TERM(TERM)
            msat_assert_formula(env, TERM)

        # Impose a timeout of 3.0 seconds
        CALLBACK = Timer(3.0)
        msat_set_termination_test(env, CALLBACK)

        with create_minimize(env, "objective", lower="23", upper="100") as obj:
            assert_objective(env, obj)

            solve(env)                    # optimization search until timeout
            get_objectives_pretty(env)    # print latest range of optimization search

            load_model(env, obj)          # retrieve sub-optimal model
            dump_model(env)               # print sub-optimal model

这是优化搜索的详细输出：

# obj(.cost_0) := objective
# obj(.cost_0) - search start: [ 23, 100 ]
# obj(.cost_0) - linear step: 1
# obj(.cost_0) -  new: 46
# obj(.cost_0) -  update upper: [ 23, 46 ]
# obj(.cost_0) - linear step: 2
# obj(.cost_0) -  new: 130/3
# obj(.cost_0) -  update upper: [ 23, 130/3 ]
# obj(.cost_0) - linear step: 3
# obj(.cost_0) -  new: 40
# obj(.cost_0) -  update upper: [ 23, 40 ]
# obj(.cost_0) - linear step: 4
# obj(.cost_0) -  new: 119/3
# obj(.cost_0) -  update upper: [ 23, 119/3 ]
# obj(.cost_0) - linear step: 5
# obj(.cost_0) -  new: 112/3
# obj(.cost_0) -  update upper: [ 23, 112/3 ]
# obj(.cost_0) - linear step: 6
# obj(.cost_0) -  new: 104/3
# obj(.cost_0) -  update upper: [ 23, 104/3 ]
# obj(.cost_0) - linear step: 7
# obj(.cost_0) -  new: 34
# obj(.cost_0) -  update upper: [ 23, 34 ]
# obj(.cost_0) - linear step: 8
# obj(.cost_0) -  new: 133/4
# obj(.cost_0) -  update upper: [ 23, 133/4 ]
# obj(.cost_0) - linear step: 9
# obj(.cost_0) -  new: 161/5
# obj(.cost_0) -  update upper: [ 23, 161/5 ]
# obj(.cost_0) - linear step: 10
# obj(.cost_0) -  new: 32
# obj(.cost_0) -  update upper: [ 23, 32 ]
# obj(.cost_0) - linear step: 11
# obj(.cost_0) -  new: 158/5
# obj(.cost_0) -  update upper: [ 23, 158/5 ]
# obj(.cost_0) - linear step: 12
# obj(.cost_0) -  new: 247/8
# obj(.cost_0) -  update upper: [ 23, 247/8 ]
# obj(.cost_0) - linear step: 13
# obj(.cost_0) -  new: 123/4
# obj(.cost_0) -  update upper: [ 23, 123/4 ]
# obj(.cost_0) - linear step: 14
# obj(.cost_0) -  new: 61/2
# obj(.cost_0) -  update upper: [ 23, 61/2 ]
# obj(.cost_0) - linear step: 15
unknown                                       ;; <== Timeout!
(objectives
  (objective 61/2), partial search, range: [ 23, 61/2 ]
)                                             ;; sub-optimal value, latest search interval

  course_load__ARRAY__1 : 9                   ;; and the corresponding sub-optimal model
  course_load__ARRAY__2 : 1
  course_load__ARRAY__3 : 2
  course_load__ARRAY__4 : 10
  course_load__ARRAY__5 : 3
  course_load__ARRAY__6 : 4
  course_load__ARRAY__7 : 1
  course_load__ARRAY__8 : 10
  course_load__ARRAY__9 : 4
  course_load__ARRAY__10 : 1
  course_load__ARRAY__11 : 1
  course_load__ARRAY__12 : 5
  course_load__ARRAY__13 : 10
  course_load__ARRAY__14 : 9
  course_load__ARRAY__15 : 1
  ...
  ;; the sub-optimal model is pretty long, it has been cut to fit this answer!
  ...

Z3 优化超时

Timeout for Z3 Optimize

optimization

timeout

z3

z3py

optimathsat

你最好的选择

总结