python - 如何将 CP-SAT 公式(Python 中)中的目标指定为所有决策变量值的最大值的最小化？

Question

我正在尝试实现一个简单的 CP-SAT，其目标是最小化所有决策变量分配的最大值。我可以最小化任何单个变量或变量的线性函数，但似乎我无法最小化变量的最大值。有办法实现这一点吗？也许是一种线性化 max() 函数的方法？

注意:我的模型确实有限制，但我在这里省略它们，因为我不认为它们与我的问题相关。

from ortools.sat.python import cp_model

model = cp_model.CpModel()

num_vars = 50
variables = {}
for i in range(num_vars):
     variables[i] = model.NewIntVar(0,i,'n_%i'% i)

下面的行总是会导致错误，其他参数(例如迭代器)也是如此。

model.Minimize(max(variables))

Answer 1

我已经找到了解决这个问题的方法。我需要声明一个新的决策变量，代表目标值，然后我需要一个 AddMaxEquality 约束，使新变量等于其他决策变量的最大值。最后，我将新的目标变量传递给 model.Minimize() 命令。

obj = model.NewIntVar(0,num_vars,'obj')

# Impose a constraint equating the new variable to the max of other vars.
model.AddMaxEquality(obj, [variables[i] for i in range(num_vars)])

# Minimize objective.
model.Minimize(obj)