z3py：按字典顺序破坏对称性约束

Question

我有两个整数变量数组（它们表示二维空间坐标），一个是另一个的对称配置。为了打破对称性，我想检查第一个数组（我们称它为 P）描述的找到的解决方案相对于对称解决方案是按字典顺序排列的（因此我可以丢弃对称解决方案）。无论如何，我在编写这个检查字典顺序的函数时遇到了问题：

到目前为止（但它是不正确的），我想到了这个：

from z3 import *
from math import ceil

width = 8
blocks = 4
x = [3, 3, 5, 5]
y = [3, 5, 3, 5]

# [blocks x 2] list of integer variables
P = [[Int("x_%s" % (i + 1)), Int("y_%s" % (i + 1))]
     for i in range(blocks)]

# value/ domain constraint
values = [And(0 <= P[i][0], P[i][0] + x[i] <= width, 0 <= P[i][1])  # , P[i][1] + y[i] <= height)
          for i in range(blocks)]

# no overlap constraint
no_overlap = [Or(i == j,  # indices must be different
                 Or(P[j][0] + x[j] <= P[i][0],  # left
                    P[j][0] >= P[i][0] + x[i],  # right
                    P[j][1] + y[j] <= P[i][1],  # down
                    P[j][1] >= P[i][1] + y[i]  # up
                    ))
              for j in range(blocks) for i in range(blocks)]


# Return maximum of a vector; error if empty
def symMax(vs):
    maximum = vs[0]
    for value in vs[1:]:
        maximum = If(value > maximum, value, maximum)
    return maximum


obj = symMax([P[i][1] + y[i] for i in range(blocks)])


def symmetric(on_x, on_y):
    if on_x and on_y:
        return [[width - P[block][0] - x[block], obj - P[block][1] - y[block]] for block in range(blocks)]
    elif on_x:
        return [[width - P[block][0] - x[block], P[block][1]] for block in range(blocks)]
    elif on_y:
        return [[P[block][0], obj - P[block][1] - y[block]] for block in range(blocks)]

#function I want to emulate
def lexicographic_order(a1, a2):
    for a, b in zip(a1, a2):
        if a < b:
            return True
        if a > b:
            return False
    return True

# my attempt: raise error "Z3 AST expected"
def lexSymb(a1, a2):
    for a, b in zip(a1, a2):
        tmp = If(a < b, True, False)
    if tmp.eq(True):
        return True
    tmp = If(a > b, False, True)
    if tmp.eq(False):
        return False
return True

lex_x = lexSymb1(P, symmetric(True, False))
lex_y = lexSymb1(P, symmetric(False, True))
lex_xy = lexSymb1(P, symmetric(True, True))

board_problem = values + no_overlap + lex_x + lex_y + lex_xy

o = Optimize()
o.add(board_problem)
o.minimize(obj)

if o.check() == sat:
    print("Solved")

elif o.check() == unsat:
    print("The problem is unsatisfiable")
else:
    print("Unexpected behaviour")

让我知道是否有可能以与符号表达式一起使用的方式修改“lexicographic_order()”，或者是否有另一种我没见过的解决方法。

Answer 1

你说你想要一个符号版本：

def lexicographic_order(a1, a2):
    for a, b in zip(a1, a2):
        if a < b:
            return True
        if a > b:
            return False
    return True

我认为这不是您想要的。为什么？请注意，在 Python 中， return 会立即退出该函数。因此，这只会比较这些列表的第一个元素（假设它们是非空的），并立即 return 。我不认为这是你想要的。

字典顺序通常意味着您必须比较整个列表。这就是你如何象征性地编码：

# Does a1 come before a2 lexicographically?
# We assume a1 != a2. If same, the algorithm will produce True.
def precedes(a1, a2):
    if not a1:
        return True
    if not a2:
        return False
    return Or(a1[0] < a2[0], And(a1[0] == a2[0], precedes(a1[1:], a2[1:])))

看看这个函数是如何工作的很有启发性。先说一个具体的数值：

> print(precedes([1,2,3],[4,5,6]))
Or(True,
   And(False,
       Or(True, And(False, Or(True, And(False, True))))))

请注意，我们构建如果第一个列表按字典顺序排列在第二个列表之前“计算”的 AST。上面的表达式简化为 True 因为你可以很容易地验证自己，但是我们不计算 True，我们构建的表达式的值将是 True.当我们运行它在符号值上时，这种结构的重要性变得显而易见：

> print(precedes([Int('a'), Int('b')], [Int('c'), Int('d')]))
Or(a < c, And(a == c, Or(b < d, And(b == d, True))))

现在您可以看到该值是如何“象征性地”计算的，并执行您希望它执行的操作：当第一个列表按字典顺序排在第二个列表之前时，它将计算为 True。当您断言这是对求解器的事实时，它会在模型上施加该约束。

希望这能让你继续前进。您需要考虑“构建”符号表达式，因此 Python 的内部 if-then-else 不是您可以使用的东西，因为它不能正确处理符号值。

z3py：按字典顺序破坏对称性约束

z3py: Symmetry breaking constraint by lexicographic order

z3

smt

z3py

lexicographic

lexicographic-ordering