如何最小化列总和的最大值？

Question

我试图解决的问题很简单（我猜 :)），但因为我是 z3 的新手，所以我总是遇到编译错误。

我的问题：

[ [var_0_1, var_0_2, var_0_3,...]
, [var_1_1, var_1_2, var_1_3,...]
, [var_2_1, var_2_2, var_2_3,...]
]

我的 objective 是对列的值求和，然后发现所有总和的最大值，然后最小化该值并再次这样做，直到无法最小化更多的最大值所有列的总和...

我希望你能理解我的问题，因为我的英语不是很好 :)

提前致谢！

Answer 1

函数最小值(最大值()):

def maxi(a,b):
  return If(a>=b,a,b)

a = 0
for y in zip(*time): #time is a list with many rows and columns
  z = sum(y)         #z receives the sum of the columns
  a = maxi(a,z)     

o.minimize(a)

Answer 2

最初，我以为你是想解决一些minmax()问题，因为你说你想解决

minimize(max(sum(var01,Var11,Var21),sum(var02,Var12,Var22), etc...))

在评论中。然而，进一步的需求引出清楚地表明它不可能是 minmax() 的实例，所以我放弃了这个想法，没有再考虑它。

现在，您自己发布的解决方案是伪装的 maxmin() 实例。我不确定这是否真的解决了您最初的问题。但是，如果是这种情况，那么我建议您尝试使用以下编码而不是基于 ite 的解决方案 [参考文献：tacas15, tacas15_extended].

(注：cost应该是一个新的和cost_i同类型的变量，声明是为了解决maxmin()目标。每隔 cost_i 从 objective 降级为一个简单的术语)

我相信这种方法有可能比另一种方法表现得更好。

编辑： 源代码示例 a = 0：

goal = Real("cost")
for y in zip(*time):
    s.add(sum(y) <= goal)
result = s.minimize(goal)

如果你想复制 a = 50:

的情况

goal = Real("cost")
for y in zip(*time):
    s.add(sum(y) <= goal)
s.add(50 <= goal)
result = s.minimize(goal)

如何最小化列总和的最大值？

How can I minimize the max of the sum of my columns?

z3

z3py