OR-Tools CP-SAT求解器：如何获取非零决策变量的最小值

要计算排除0值后的决策变量最小值，不能直接用AddMinEquality（它会包含所有变量），需要通过约束逻辑来实现只考虑非0变量的最小值：

核心思路 #

1. 对于每个标记为非0的变量（bool_dvs[i] = 1），强制minimum_dv小于等于该变量的值，保证它是所有非0变量的下界。
2. 强制minimum_dv至少等于一个非0变量的值，确保它是真实的最小值而非更小的数。
3. 调整minimum_dv的下界为1，因为非0变量都满足dvs[i] > 0，避免0被纳入结果。

修改后的完整代码 #

from ortools.sat.python import cp_model

model = cp_model.CpModel()

dvs = {}
for i in range(5):
    dvs[i] = model.NewIntVar(lb=0, ub=100, name=f"dv_{i}")
    
# 创建与整数变量绑定的布尔变量
bool_dvs = {i : model.NewBoolVar(f"bool_{i}") for i in range(5)}
model.Add(bool_dvs[0] + bool_dvs[1] == 0)
model.Add(bool_dvs[2] + bool_dvs[3] + bool_dvs[4] == 3)
    
# 布尔变量与整数变量的约束：bool=0则dv=0；bool=1则dv>0
for i in range(5):
    model.Add(dvs[i] == 0).OnlyEnforceIf(bool_dvs[i].Not())
    model.Add(dvs[i] > 0).OnlyEnforceIf(bool_dvs[i])

# 确保后三个变量互不相同
model.AddAllDifferent([dvs[2], dvs[3], dvs[4]])

# 创建存储非0变量最小值的变量，下界设为1（因为非0变量都>0）
minimum_dv = model.NewIntVar(lb=1, ub=100, name="minimum_dv")

# 添加约束：对于每个非0变量，minimum_dv <= dvs[i]
for i in range(5):
    # 当bool_dvs[i] = 1时，强制minimum_dv <= dvs[i]；bool_dvs[i]=0时该约束不生效
    model.Add(minimum_dv <= dvs[i]).OnlyEnforceIf(bool_dvs[i])

# 添加约束：minimum_dv至少等于一个非0变量的值
# 引入辅助布尔变量，标记minimum_dv是否等于对应dvs[i]
is_min = {i: model.NewBoolVar(f"is_min_{i}") for i in range(5)}
for i in range(5):
    # 当bool_dvs[i]=1时，is_min[i] = 1 等价于 minimum_dv == dvs[i]
    model.Add(minimum_dv == dvs[i]).OnlyEnforceIf([bool_dvs[i], is_min[i]])
    # 当bool_dvs[i]=0时，is_min[i]必须为0
    model.Add(is_min[i] == 0).OnlyEnforceIf(bool_dvs[i].Not())

# 至少有一个is_min[i]为1，保证minimum_dv是某个非0变量的值
model.Add(sum(is_min.values()) >= 1)

model.Minimize(sum(dvs[i] for i in range(5)))

solver = cp_model.CpSolver()
status = solver.solve(model)

print([solver.Value(dvs[i]) for i in range(5)])
print([solver.Value(bool_dvs[i]) for i in range(5)])
print(solver.Value(minimum_dv))

代码说明 #

• 替换了原有的AddMinEquality，改用分约束实现非0变量的最小值计算。
• 通过OnlyEnforceIf控制约束仅对非0变量生效，避免0值干扰。
• 辅助布尔变量is_min确保minimum_dv确实等于某个非0变量的值，而不是随便一个更小的数。

运行后，输出的minimum_dv会是排除0后的最小值，比如示例场景中会得到1（因为求解器会让非0变量取最小的不同值1、2、3）。

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