Gurobi排班模型班次变更计数与实际不符问题求助

你当前的c_{it}变量只做了单向约束绑定：仅规定“发生班次变更时c_{it}必须为1”，但没有反向限制“c_{it}=1时必须存在班次变更”。当Nr_max设置得足够大（比如9），模型在优化时没有动力将多余的c_{it}设为0——因为这些变量取1既不违反变更次数上限，也不影响其他约束或目标函数，因此会生成虚假的变更记录。

举个具体场景：员工i在t和t+1天班次完全相同，原约束仅允许c_{it}取0或1，却没强制它必须为0。当Nr_max远大于实际所需变更数时，Gurobi会给这类c_{it}赋值1，因为这是合法的可行解。

需要给c_{it}添加双向约束，让它和实际班次变更严格绑定，有两种实现方式：

方式1：使用二次约束（更简洁） #

Gurobi支持二次约束，直接通过二次项关联班次变量和变更变量：

1. 首先在模型参数中开启非凸二次约束支持：

   model.setParam('NonConvex', 2)
   

2. 添加双向绑定约束：

   # 遍历每个员工和每个可能发生变更的时段（t从1到T-1，对应t到t+1天）
   for i in workers:
       for t in range(1, T):
           # c_it = 1 - 员工i在t和t+1天当班同班次的情况
           same_shift = gurobi.quicksum(x[i,t,k] * x[i,t+1,k] for k in shifts)
           model.addConstr(c[i,t] == 1 - same_shift, name=f"bind_change_{i}_{t}")
   

3. 保留原有的变更次数上限约束：

   for i in workers:
       model.addConstr(gurobi.quicksum(c[i,t] for t in range(1, T)) <= Nr_max, name=f"max_changes_{i}")
   

方式2：线性化约束（避免二次项） #

如果不想使用二次约束，可通过引入辅助变量y_{itk}线性化：

1. 定义辅助变量y_{itk}（表示员工i在t天和t+1天都值k班）：

   y = model.addVars(workers, range(1, T), shifts, vtype=gurobi.GRB.BINARY, name="same_shift")
   

2. 添加辅助变量的线性约束：

   for i in workers:
       for t in range(1, T):
           for k in shifts:
               # y_itk只能在x_itk和x_i(t+1)k都为1时取1
               model.addConstr(y[i,t,k] <= x[i,t,k], name=f"y_bound1_{i}_{t}_{k}")
               model.addConstr(y[i,t,k] <= x[i,t+1,k], name=f"y_bound2_{i}_{t}_{k}")
               model.addConstr(y[i,t,k] >= x[i,t,k] + x[i,t+1,k] - 1, name=f"y_bound3_{i}_{t}_{k}")
           # 绑定c_it和同班次情况：c_it + 同班次总数 = 1
           model.addConstr(c[i,t] + gurobi.quicksum(y[i,t,k] for k in shifts) == 1, name=f"bind_change_{i}_{t}")
   

3. 同样保留变更次数上限约束。

修改约束后，测试不同Nr_max值：

• 当Nr_max小于实际所需变更数时，模型应返回不可行（或按你的目标函数调整）
• 当Nr_max大于等于实际变更数时，“Changes Worker X”列表中1的数量必须和实际班次变更次数完全一致

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