Pulp约束不满足：同一椅位患者作业时间重叠问题排查

问题背景 #

使用Pulp求解患者-护士-椅位分配优化问题，核心要求是同一椅位的患者作业时间不可重叠。已定义决策变量：

• x[(p_id, n_id)]：二进制变量，标记患者p是否分配给护士n
• y[(p_id, c)]：二进制变量，标记患者p是否分配给椅位c
• start_times[p_id]：连续变量，记录患者p的作业开始时间

已实现“每位患者仅分配1名护士和1个椅位”的约束，但同一椅位时间不重叠的约束未生效，出现如下重叠情况：

Chair 3 schedule:
Patient 0: 08:20 - 09:20
Patient 4: 09:10 - 10:10
Patient 6: 10:10 - 12:10

约束失效原因 #

原约束代码存在逻辑错误：

for c in range(num_chairs):
    for t in range(open_time, close_time):
        prob += pulp.lpSum([y[p['id'], c] for p in patients if
                            (start_times[p['id']] <= t <= start_times[p['id']] + p['duration'])]) <= 1

这里的if (start_times[p['id']] <= t <= start_times[p['id']] + p['duration'])是在构建约束阶段执行的条件判断，但start_times是决策变量，求解前无具体数值，该条件会基于变量初始状态（通常为0）筛选患者，导致实际添加的约束完全不符合需求，相当于未对时间重叠做有效限制。

正确约束实现方法 #

采用大M法将“同一椅位患者时间不重叠”的逻辑转化为线性约束，步骤如下：

1. 定义大M值：取诊所营业总时长（确保大于任何患者的作业时长）
2. 对每一对不同患者、每个椅位，添加约束：若两人都分配到同一椅位，则其中一人的作业结束时间必须早于另一人的开始时间

代码实现 #

# 定义大M值：取诊所营业总时长
M = close_time - open_time

for c in range(num_chairs):
    # 遍历所有患者对（避免重复处理）
    for i in range(len(patients)):
        p1 = patients[i]
        p1_id = p1['id']
        p1_duration = p1['duration']
        for j in range(i + 1, len(patients)):
            p2 = patients[j]
            p2_id = p2['id']
            p2_duration = p2['duration']
            
            # 约束1：若p1和p2都在椅位c，则p1结束时间 <= p2开始时间
            prob += start_times[p2_id] >= start_times[p1_id] + p1_duration - M * (2 - y[p1_id, c] - y[p2_id, c])
            # 约束2：若p1和p2都在椅位c，则p2结束时间 <= p1开始时间
            prob += start_times[p1_id] >= start_times[p2_id] + p2_duration - M * (2 - y[p1_id, c] - y[p2_id, c])

约束逻辑说明 #

• 当y[p1_id, c]和y[p2_id, c]都为1（两人都分配到椅位c），2 - y[p1_id, c] - y[p2_id, c] = 0，约束简化为：
  start_times[p2_id] >= start_times[p1_id] + p1_duration 或 start_times[p1_id] >= start_times[p2_id] + p2_duration，确保时间不重叠
• 若其中任意一人未分配到椅位c（y为0），M * (2 - ...)会是一个很大的正数，约束自动满足，不会对变量产生限制

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