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

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

1 голос
/ 25 апреля 2020

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

1 Ответ

1 голос
/ 26 апреля 2020

Я нашел решение этой проблемы. Мне нужно было объявить новую переменную решения, представляющую объективное значение, а затем мне понадобилось ограничение AddMaxEquality, приравнивающее новую переменную к максимуму других переменных решения. Наконец, я передаю новую переменную target в команду 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)
...