如何修改OR-Tools CP-Sat惩罚性覆盖约束为目标导向双向惩罚

问题背景 #

我正在Python中使用OR-Tools的CP-Sat模块开发调度器，参考的原代码（C#版本）仅针对每日班次的人员超额情况进行惩罚。我需要扩展该逻辑，使其以minDemand为目标值，同时惩罚人员不足与超额，理想情况下采用成本递增机制——偏离目标越远，惩罚成本越高。但之前的尝试均导致模型出现INFEASIBLE或UNKNOWN状态，寻求可行的解决方案。

原代码核心逻辑（C#）：

// Cover constraints
foreach (int s in Range(1, numShifts))
{
    foreach (int w in Range(numWeeks))
    {
        foreach (int d in Range(7))
        {
            var works = new BoolVar[numEmployees];
            foreach (int e in Range(numEmployees))
            {
                works[e] = work[e, s, w * 7 + d];
            }

            var minDemand = weeklyCoverDemands[d][s - 1];
            var worked = model.NewIntVar(minDemand, numEmployees, "");
            model.Add(LinearExpr.Sum(works) == worked);

            var overPenalty = excessCoverPenalties[s - 1];
            if (overPenalty > 0)
            {
                var name = $"excess_demand(shift={s}, week={w}, day={d}";
                var excess = model.NewIntVar(0, numEmployees - minDemand, name);
                model.Add(excess == worked - minDemand);
                obj.AddTerm(excess, overPenalty);
            }
        }
    }
}

核心问题分析 #

原代码存在一个关键限制：将worked变量的下界设为minDemand，这相当于强制班次人员数必须满足最低需求，直接禁止了人员不足的情况。这也是之前尝试添加不足惩罚时模型不可行的根本原因——约束之间存在矛盾。

解决方案（Python实现） #

步骤1：调整变量范围，允许人员不足 #

首先移除worked变量的下界限制，使其范围覆盖0到numEmployees，允许人员数低于minDemand。

步骤2：拆分偏差变量，分别表示不足与超额 #

定义两个新变量：

• shortage：人员不足的数量（当worked < minDemand时，等于minDemand - worked，否则为0）
• excess：人员超额的数量（当worked > minDemand时，等于worked - minDemand，否则为0）

通过约束worked + shortage = min_demand + excess关联三者，确保两个偏差变量不会同时为正（逻辑上自动满足）。

步骤3：添加惩罚逻辑（线性/递增可选） #

• 线性惩罚：直接给shortage和excess乘以对应惩罚系数，加入目标函数。
• 递增惩罚：通过布尔变量分段表示偏差程度，每段对应更高的惩罚成本，实现偏离越远惩罚越高的效果。

完整代码示例 #

from ortools.sat.python import cp_model

# 假设已提前定义以下变量：
# numEmployees: 员工总数
# numShifts: 班次类型数
# numWeeks: 调度周数
# weeklyCoverDemands: 每日各班次的需求矩阵，格式为[周几][班次]
# excessCoverPenalties: 各班次的基础超额惩罚系数
# shortagePenalties: 各班次的基础不足惩罚系数
# work: 布尔变量数组，work[e][s][d]表示员工e是否在第d天的班次s工作

model = cp_model.CpModel()
objective = model.NewIntVar(0, 10**9, "total_penalty")
model.Minimize(objective)

for shift in range(numShifts):
    for week in range(numWeeks):
        for day in range(7):
            # 收集当天该班次所有员工的工作状态
            works = [work[emp][shift][week * 7 + day] for emp in range(numEmployees)]
            min_demand = weeklyCoverDemands[day][shift]

            # 1. 调整worked变量范围，允许人员数低于需求
            worked = model.NewIntVar(
                0, numEmployees,
                f"worked_shift{shift}_week{week}_day{day}"
            )
            model.Add(cp_model.LinearExpr.Sum(works) == worked)

            # 2. 定义不足和超额变量
            max_shortage = min_demand
            max_excess = numEmployees - min_demand
            shortage = model.NewIntVar(
                0, max_shortage,
                f"shortage_shift{shift}_week{week}_day{day}"
            )
            excess = model.NewIntVar(
                0, max_excess,
                f"excess_shift{shift}_week{week}_day{day}"
            )

            # 关联worked、shortage、excess的约束
            model.Add(worked + shortage == min_demand + excess)

            # 3. 添加线性惩罚到目标函数
            over_penalty = excessCoverPenalties[shift]
            under_penalty = shortagePenalties[shift]
            if over_penalty > 0:
                model.AddTerm(excess, over_penalty, objective)
            if under_penalty > 0:
                model.AddTerm(shortage, under_penalty, objective)

            # 可选：添加递增惩罚（示例为超额每多1人，惩罚系数翻倍）
            if over_penalty > 0 and max_excess > 0:
                for k in range(1, max_excess + 1):
                    # 布尔变量表示是否超额至少k人
                    excess_k = model.NewBoolVar(
                        f"excess_k{k}_shift{shift}_week{week}_day{day}"
                    )
                    model.Add(excess >= k).OnlyEnforceIf(excess_k)
                    model.Add(excess < k).OnlyEnforceIf(excess_k.Not())
                    # 每多超额1人，惩罚增加over_penalty * k（可自定义递增规则）
                    model.AddTerm(excess_k, over_penalty * k, objective)

            # 可选：不足的递增惩罚
            if under_penalty > 0 and max_shortage > 0:
                for k in range(1, max_shortage + 1):
                    shortage_k = model.NewBoolVar(
                        f"shortage_k{k}_shift{shift}_week{week}_day{day}"
                    )
                    model.Add(shortage >= k).OnlyEnforceIf(shortage_k)
                    model.Add(shortage < k).OnlyEnforceIf(shortage_k.Not())
                    model.AddTerm(shortage_k, under_penalty * k, objective)

关键注意事项 #

• 变量范围合理性：确保shortage的上界为min_demand，excess的上界为numEmployees - min_demand，避免变量范围过大导致求解器性能下降或状态异常。
• 递增惩罚的实现：通过布尔变量分段模拟递增成本，符合CP-Sat的线性约束要求，避免使用非线性函数导致求解器无法处理。
• 约束冲突排查：如果仍出现INFEASIBLE状态，需检查其他业务约束（如员工排班限制）是否与新的偏差约束冲突，逐步简化约束定位问题。

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