pythonor-toolscp-sat

CP-SAT | OR-Tools: Select max. 5 out of 10 total options?

I have an optimization problem where I need to pick max. 5 out of 10 available options according to different criteria. I was wondering how to encode this constraint. Is any of the 3 alternative versions below better/faster than the others? If not, I would go with the first one, as it is the most concise...

# create model and 10 variables
model = CpModel()
vars = []
for i in range(10):
    vars.append(model.new_bool_var(f"var {i}"))
model.maximize(sum(v for v in vars))

# constraint: max. 5 variables can be true

# Version 1
model.add(sum(v for v in vars) <= 5)

# Version 2
var_sum = model.new_int_var(0, 5, "sum")
model.add(var_sum == sum(vars))

# Version 3
var_sum = model.new_int_var(0, 10, "sum")  # sic! -> 10
model.add(var_sum == sum(vars))
model.add(var_sum <= 5)

# ...aaand solve it
solver = CpSolver()
solver.solve(model)
print(solver.objective_value)
Solution

  • They will all be equivalent after presolve.

    I would use the first option.