CP-SAT | OR-Tools：10个选项中最多选5个的约束编码方案对比

我遇到一个优化问题，需要依据不同准则从10个可用选项中最多选择5个。想了解如何编码该约束，以下三种实现版本中哪种性能更优？若无差异，我会选用最简洁的第一种方案。

# 创建模型和10个布尔变量
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))

# 约束：最多5个变量为True

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

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

# 版本3
var_sum = model.new_int_var(0, 10, "sum")  # 注意：上限设为10
model.add(var_sum == sum(vars))
model.add(var_sum <= 5)

# 求解模型
solver = CpSolver()
solver.solve(model)
print(solver.objective_value)

性能与选型分析 #

• 版本1：最简洁直观的写法，直接对布尔变量的和添加<=5的约束。这是推荐的最优写法，代码可读性强，无需额外变量，求解器能直接处理该约束。
• 版本2：通过一个上限为5的整数变量绑定布尔和，本质上等价于版本1（因为变量上限已经限制了总和不超过5），但多创建了一个不必要的中间变量，代码冗余，没有性能优势。
• 版本3：先创建上限为10的整数变量，再额外添加<=5的约束，逻辑上完全等同于版本1。求解器会自动简化这种冗余的中间变量约束，因此性能上和版本1无差异，但代码更繁琐。

结论：三种版本在求解性能上没有显著差异，因为CpSolver会对约束进行内部优化。优先选择版本1，它既简洁又易于维护。

内容的提问来源于stack exchange，提问作者Leszek Pachura