如何改进 Z3py 中基于二分搜索的优化

Question

我正在尝试使用 Z3py 优化基于最小化的集合覆盖问题 (SCP41) 实例。

结果如下：

正在使用

(1) 我知道Z3支持优化(https://rise4fun.com/Z3/tutorial/optimization)。很多时候我在 SCP41 和其他实例中达到了最佳状态，有一些没有。

(2) 我知道如果我使用 Z3py API 而没有优化模块，我将不得不进行 (Minimum and maximum values of integer variable) @Leonardo de Moura。它从来没有给我结果。

我的做法

(3) 我试图通过实现二进制搜索来改进顺序搜索方法，类似于它在 (Does Z3 have support for optimization problems) 中解释@Philippe 的方式，当我运行我的算法等待并且我没有得到任何结果。

我知道二进制搜索应该更快并且在这种情况下工作？我也知道 SCP41 实例很大，产生了很多限制，它变得非常组合，这是我的完整代码 (Code large instance) 这是我的二进制搜索：

def min(F, Z, M, LB, UB, C):    
    i = 0
    s = Solver()

    s.add(F[0])
    s.add(F[1])
    s.add(F[2])
    s.add(F[3])
    s.add(F[4])
    s.add(F[5])

    r = s.check()

    if r == sat:
        UB = s.model()[Z]

        while int(str(LB)) <= int(str(UB)):

            C = int(( int(str(LB)) + int(str(UB)) / 2))

            s.push()
            s.add( Z > LB, Z <= C)

            r = s.check()

            if r==sat:
                UB = Z
                return s.model()
            elif r==unsat:
                LB = C
                s.pop()

            i = i + 1
            if (i > M):
                raise Z3Exception("maximum not found, maximum number of iterations was reached")
    return unsat

而且，这是我在初始测试中使用的另一个实例 (Code short instance)，它在任何情况下都运行良好。

什么是不正确的二分查找或未正确应用 Z3 的某些概念？

此致，亚历克斯

Answer 1

我认为您的问题与最小化本身无关。如果您在程序中的 r = s.check() 之后放置 print r，您会看到 z3 只是努力获得 return 结果。所以你的循环甚至不执行一次。

你的程序太大了，没法读完！但是我看到了很多形式的东西：

 Or(X250 == 0, X500 == 1)

这表明您的变量 X250 X500 等（还有很多）实际上是布尔值，而不是整数。如果那确实是真的，那么您绝对应该坚持使用布尔值。解决整数约束比解决纯布尔约束要困难得多，并且当您像这样使用整数对布尔建模时，底层求解器只会探索无法访问的搜索 space。

如果情况确实如此，即，如果您使用 Int 值对布尔值建模，我强烈建议对您的问题建模以摆脱 Int 值，只使用布尔值。如果您提出 "small" 个问题实例，我们可以帮助建模。

如果您确实需要 Int 个值（很可能就是这种情况），那么我会说您的问题对于 SMT 求解器来说太难有效地处理了。您最好使用针对此类优化问题调整的其他系统。

如何改进 Z3py 中基于二分搜索的优化

How to improve binary search based optimization in Z3py

z3

z3py

sat-solvers