Z3 可以解决 MILP 优化问题吗？能输出top N最好的结果吗？

Question

我正在处理一个 MILP 问题，我需要输出前 N 个最好的结果。有人建议使用 Z3 求解器，因为我以前从未使用过这个求解器，而且我查看了一些文档，似乎它不是像 Gurobi/cbc 这样常见的优化求解器。有人可以帮忙吗？如果可能的话，可以在python中提供任何例子吗？非常感谢！

Answer 1

您可以使用 Z3 解决 MILP 个问题：

from z3 import *

# https://theory.stanford.edu/~nikolaj/programmingz3.html#sec-optimization
o = Optimize()
x, y, z, gain = Ints('x y z gain')

o.add(2*x + 3*y + z == 100)
o.add(x + 2*y + 4*z == 25)
o.add(gain == 4*x + 7*y + 1*z)
o.maximize(gain)
    
noOfSolutions = 0
while (noOfSolutions < 10) and (o.check() == sat):
    noOfSolutions = noOfSolutions + 1
    model = o.model()
    print(model)
    #  go for the next solution with reduced gain
    o.add(gain < model.eval(gain))

请注意，此代码不会为 gain 找到具有相同非递减值的解决方案。为此，必须添加更复杂的约束以防止再次选择先前的解决方案。

查看 and here 讨论替代方案。

Z3 可以解决 MILP 优化问题吗？能输出top N最好的结果吗？

Can Z3 solve a MILP optimization problem? Can it output the top N best result?

python

z3