CODEWITHSUNDEEP
pythonoptimizationor-toolsconstraint-programmingcp-sat
Gord B
Gord B

Reputation: 71

How can I specify the objective in a CP-SAT formulation (in python) to be the minimization of the max of all decision variable values?

I am attempting to implement a simple CP-SAT where the objective is to minimize the largest value assigned across all decision variables. I can minimize any individual variable or a linear function of variables, but it seems I am unable to minimize the maximum of variables. Is there a way to achieve this? Perhaps a way to linearize a max() function?

Note: I do have constraints in my model, but I'm omitting them here as I do not believe they are relevant to my question. 

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)

The following line always results in an error, as does alternative arguments, e.g., an iterator.

model.Minimize(max(variables))

Upvotes: 3

Views: 1177

Answers (1)

Gord B
Gord B

Reputation: 71

I've discovered a solution to this problem. I needed to declare a new decision variable, representing the objective value, and then I needed an AddMaxEquality constraint, equating the new variable to the max of other decision variables. Finally, I pass the new objective variable to the model.Minimize() command. 

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)

Upvotes: 4

Related Questions