Как я могу указать цель в формулировке CP-SAT (в python) как минимизацию максимума всех значений переменных решения?

Я пытаюсь реализовать простой 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))

python optimization max or-tools constraint-programming
person Gord B    schedule 25.04.2020    source источник
comment
Вторая половина вашего вопроса, где вы описываете, как вы исправили ошибку, может быть использована в качестве ответа.   -  person Zach Valenta    schedule 25.04.2020
comment
Извините, я новичок в Stack Overflow :). Не был уверен, какой протокол был правильным, когда нашел ответ на свой вопрос. Я ввел ответ ниже вместо того, чтобы отредактировать вопрос.   -  person Gord B    schedule 26.04.2020

Ответы (1)


arrow_upward
3
arrow_downward

Я нашел решение этой проблемы. Мне нужно было объявить новую переменную решения, представляющую целевое значение, а затем мне понадобилось ограничение 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)
person Gord B    schedule 26.04.2020
comment
Спасибо! Пытались разобраться с этим целую вечность. - person Greg Cowell; 23.12.2020