在混合整数规划（MIP）中实现两任务无重叠约束

要在MIP中实现两个任务的不重叠约束，核心思路是通过二进制变量+大M线性约束枚举两种不重叠的可能性：要么任务1完全在任务2结束后开始，要么任务2完全在任务1结束后开始。

实现原理 #

两个任务不重叠的逻辑等价于以下两种情况至少满足其一：

• 任务1的开始时间 ≥ 任务2的结束时间（任务2先完成）
• 任务2的开始时间 ≥ 任务1的结束时间（任务1先完成）

由于MIP仅支持线性约束，我们需要引入一个二进制决策变量y（取值0或1）来切换两种情况，再用大M法将逻辑约束转化为线性约束：

• 当y=1时，强制任务1在任务2之后开始：s1 ≥ s2 + d2
• 当y=0时，强制任务2在任务1之后开始：s2 ≥ s1 + d1

对应的线性约束表达式为：

s1 ≥ s2 + d2 - M*(1 - y)
s2 ≥ s1 + d1 - M*y

其中M是一个足够大的常数（需大于所有可能的时间差上限，比如所有任务的最大可能结束时间之和），确保二进制变量取对应值时约束生效，反之约束自动松弛。

代码实现（以开源求解器PuLP为例） #

假设s1、s2是模型中的连续决策变量（任务开始时间），d1、d2是已知的任务持续时间，具体实现如下：

from pulp import LpProblem, LpVariable, LpMinimize, LpBinary

# 已知的任务持续时间
d1 = 10
d2 = 5

# 创建MIP模型
model = LpProblem("NoOverlapTask", LpMinimize)

# 定义决策变量：任务开始时间（非负连续变量）
s1 = LpVariable("s1", lowBound=0)
s2 = LpVariable("s2", lowBound=0)

# 定义二进制变量：控制任务先后顺序
y = LpVariable("y", cat=LpBinary)

def no_overlap(model, s1, d1, s2, d2, y):
    # 设置足够大的M，这里假设最大时间范围为100（可根据实际场景调整）
    M = 100
    # 添加不重叠约束
    model += s1 >= s2 + d2 - M * (1 - y), "Task1AfterTask2"
    model += s2 >= s1 + d1 - M * y, "Task2AfterTask1"

# 调用函数添加约束
no_overlap(model, s1, d1, s2, d2, y)

# 示例目标函数：最小化最晚完成时间
model += max(s1 + d1, s2 + d2)

# 求解模型
model.solve()

# 输出结果
print(f"任务1开始时间：{s1.value()}，结束时间：{s1.value() + d1}")
print(f"任务2开始时间：{s2.value()}，结束时间：{s2.value() + d2}")
print(f"任务顺序控制变量y的值：{y.value()}")

关键注意点 #

• 二进制变量y的作用是在两种不重叠情况中做选择，避免冗余约束影响求解效率。
• M的取值需合理：足够大以覆盖所有可能的时间差，但不宜过大（否则会导致数值不稳定），建议取任务最大可能结束时间的2倍。
• 若需处理多任务不重叠，只需对每一对任务重复上述逻辑即可。

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