OR-Tools CP-Sat：如何高效优化变量和趋近目标均值？

你需要让多组变量的和尽可能接近目标均值，同时对更大的差值施加不成比例的重惩罚，当前的层级布尔变量方案虽有效但引入了过多变量。以下是更高效的替代方案：

方案1：直接用差值平方作为惩罚（最简实现） #

OR-Tools的AddMultiplicationEquality可直接计算差值的平方，在差值范围极小的场景下（如你的案例中diff最大为3），该方法性能开销极低，且变量数最少。

示例代码：

diff_a = model.NewIntVar(0, 3, "diff_a")
model.AddAbsEquality(diff_a, desired_sum - sum_a)
diff_a_sq = model.NewIntVar(0, 9, "diff_a_sq")
model.AddMultiplicationEquality(diff_a_sq, diff_a, diff_a)

diff_b = model.NewIntVar(0, 3, "diff_b")
model.AddAbsEquality(diff_b, desired_sum - sum_b)
diff_b_sq = model.NewIntVar(0, 9, "diff_b_sq")
model.AddMultiplicationEquality(diff_b_sq, diff_b, diff_b)

diff_c = model.NewIntVar(0, 3, "diff_c")
model.AddAbsEquality(diff_c, desired_sum - sum_c)
diff_c_sq = model.NewIntVar(0, 9, "diff_c_sq")
model.AddMultiplicationEquality(diff_c_sq, diff_c, diff_c)

objectives = [diff_a_sq, diff_b_sq, diff_c_sq]

方案2：枚举差值对应惩罚值（灵活自定义） #

若担心乘法约束的性能，或需要自定义非线性惩罚规则（如非平方的权重），可直接枚举每个差值对应的惩罚值，用OnlyEnforceIf绑定约束，变量数同样极少。

示例代码（自定义惩罚权重）：

def create_penalty_var(model, diff_var, penalty_weights):
    penalty_var = model.NewIntVar(0, max(penalty_weights), f"{diff_var.Name()}_penalty")
    # 绑定差值与对应惩罚
    for diff_value, penalty in enumerate(penalty_weights):
        model.Add(penalty_var == penalty).OnlyEnforceIf(diff_var == diff_value)
    return penalty_var

# 自定义惩罚规则：索引对应差值，值为惩罚力度
penalty_weights = [0, 1, 4, 9]  # diff=0→0，diff=1→1，diff=2→4，diff=3→9

diff_a = model.NewIntVar(0, 3, "diff_a")
model.AddAbsEquality(diff_a, desired_sum - sum_a)
penalty_a = create_penalty_var(model, diff_a, penalty_weights)

diff_b = model.NewIntVar(0, 3, "diff_b")
model.AddAbsEquality(diff_b, desired_sum - sum_b)
penalty_b = create_penalty_var(model, diff_b, penalty_weights)

diff_c = model.NewIntVar(0, 3, "diff_c")
model.AddAbsEquality(diff_c, desired_sum - sum_c)
penalty_c = create_penalty_var(model, diff_c, penalty_weights)

objectives = [penalty_a, penalty_b, penalty_c]

方案对比与选择 #

• 方案1：变量数最少，代码最简洁，适合差值范围小的场景，性能完全够用。
• 方案2：灵活性最高，可定制任意惩罚规则，避免乘法约束，性能略优于方案1。
• 你当前的层级布尔法：变量与约束数量多，仅适合差值范围极大、需动态调整层级的场景，你的案例中无需使用。

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