将项目分配给具有特征的组

Question

我在将变量分配给集合时遇到问题。每个集合都有一个可以分配给它的变量限制，每个变量都可以分配给总集合的某个子集。

示例：

a 可以在集合 A 或 B
b可以成套B
c 可以在集合 A 或 B
d可以成套A

因此，我们可以有 A: a, d; B: b, c 或 A: c, d; B: a,b（集合中变量的顺序无关紧要）。

我目前正在使用z3进行以下操作（此处使用solve编写，也可以使用Solver表示）。通过下面的代码，如果 a_in_A = True 那么变量 a 在集合 A.

中

solve(If(a_in_B, 1, 0) + If(b_in_B, 1, 0) + If(c_in_B, 1, 0) <= 2,
      If(a_in_A, 1, 0) + If(c_in_A, 1, 0) + If(d_in_A, 1, 0) <= 2, 
      If(a_in_A, 1, 0) + If(a_in_B, 1, 0) == 1, 
      If(b_in_B, 1, 0) == 1, 
      If(c_in_A, 1, 0) + If(c_in_B, 1, 0) == 1, 
      If(d_in_A, 1, 0) == 1)

我可以对集合中的变量进行加权，如下所示。在这种情况下，我们将只剩下 A: a, d; B: b, c 作为解决方案，尽管这可以扩展。

solve(If(a_in_B, 4, 0) + If(b_in_B, 3, 0) + If(c_in_B, 3, 0) <= 6,
      If(a_in_A, 4, 0) + If(c_in_A, 3, 0) + If(d_in_A, 3, 0) <= 7, 
      If(a_in_A, 4, 0) + If(a_in_B, 4, 0) == 4, 
      If(b_in_B, 3, 0) == 3, 
      If(c_in_A, 3, 0) + If(c_in_B, 3, 0) == 3, 
      If(d_in_A, 3, 0) == 3)

但是，我还想输入其他功能，例如 c 必须在 a 之后的集合中。因此，我们将减少到只有 A: a, d; B: b, c 的解决方案。我如何将这些要求添加到 z3 求解器表达式（或其他方式）？

Answer 1

与任何编程任务一样，可以有多种方法来解决这个问题。我认为以下是 z3py 中最惯用的方式。请注意内部 Set 类型的使用，它在内部由数组建模。我选择整数作为集合的元素，但如果您愿意，可以将其设为枚举类型（或其他一些基本类型）：

from z3 import *

s = Solver()

a, b, c, d = Ints('a b c d')
allElems = [a, b, c, d]
s.add(Distinct(allElems))

# We have 2 sets
A, B = Consts ('A B', SetSort(IntSort()))
allSets = [A, B]

# Generic requirement: Every element belongs to some set:
for e in allElems:
    belongs = False;
    for x in allSets:
        belongs = Or(belongs, IsMember(e, x))
    s.add(belongs)

# Capacity requirements
sizeA, sizeB = Ints('sizeA sizeB')
s.add(SetHasSize(A, sizeA))
s.add(SetHasSize(B, sizeB))
s.add(sizeA <= 2)
s.add(sizeB <= 2)

# Problem specific requirements:
s.add(Or(IsMember(a, A), IsMember(a, B)))
s.add(IsMember(b, B))
s.add(Or(IsMember(c, A), IsMember(c, B)))
s.add(IsMember(d, A))

# c must be in a set that's after a's set
s.add(Implies(IsMember(a, A), IsMember(c, B)))
s.add(Not(IsMember(a, B))) # otherwise there wouldn't be a place to put c!

r = s.check()
if r == sat:
    print(s.model())
else:
    print("Solver said: " + r)

请注意如何使用 sizeA、sizeB 变量说明 cardinality/capacity 要求。您可以概括并编写您的辅助函数来自动化大部分这些东西。

您最初的问题定义相当含糊，但我希望以上内容能让您了解如何继续。特别是，我们可以很容易地表达 c 属于集合“之后” a 的要求，因为我们周围只有两个集合：

s.add(Implies(IsMember(a, A), IsMember(c, B)))
s.add(Not(IsMember(a, B))) # otherwise there wouldn't be a place to put c!

但是如果你有两个以上的集合，你可能想要编写一个遍历集合的辅助函数（就像我在“一般要求”部分所做的那样）来自动执行此操作。（本质上，你会说如果 A 在一个特定的集合中，那么 c 在“后面”的集合中。当你来到最后一个集合时，你需要说 a 不在里面，否则就没地方放 c 了。）

当我运行上面的程序时，它打印：

[A = Lambda(k!0, Or(k!0 == 1, k!0 == 4)),
 b = 5,
 a = 1,
 d = 4,
 sizeB = 2,
 c = 3,
 sizeA = 2,
 B = Lambda(k!0, Or(k!0 == 3, k!0 == 5)),
 Ext = [else -> 5]]

这可能有点难读，但您很快就会习惯的！重要部分是：

a = 1
b = 5
c = 3
d = 4

以上应该是self-explanatory。因为我们想用整数表示元素，所以 z3 选择了这些。（请注意，我们说 Distinct 以确保它们不相同。）如果需要，您可以在此处使用 enum-sort。

下一部分是集合A和B的表示：

A = Lambda(k!0, Or(k!0 == 1, k!0 == 4)),
B = Lambda(k!0, Or(k!0 == 3, k!0 == 5)),

这就是说 A 包含元素 1 和 4（即 a 和 d），而 B 包含元素 3 和 5（即 b 和 c）。您几乎可以忽略 Lambda 部分和看起来很有趣的 k!0 符号，并按如下方式阅读它： 1 OR 4 属于的任何值A。 B.

也类似

sizeA 和 sizeB 变量应该是 self-explanatory。

您可以忽略 Ext 值。它被 z3 用于内部目的。

希望这向您展示了如何使用 built-in 对 Set 的支持以声明方式构建更复杂的约束。

将项目分配给具有特征的组

Assigning items to groups with features

algorithm

combinations

set

z3

z3py