如何用OR-Tools约束规划最大化任务-日期分配的一致对数量

问题背景 #

我们有3个有序任务[0, 1, 2]和2个有序日期[0, 1]，需要将任务分配至日期，要求最大化一致对的数量。这里的一致对定义为：若任务i的序号小于任务j（i < j），且任务i分配的日期≤任务j分配的日期，则(i,j)是一个一致对；反之则为不一致对（比如任务1分配至日期1，任务2分配至日期0）。

修正后的完整代码 #

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# 数据定义
tasks = [0, 1, 2]
days = [0, 1]

all_possible_allocations = {
    (task, day)
    for task in tasks
    for day in days
}

# 决策变量：allocation[(task, day)]为1表示该任务分配到对应日期
allocation = {
    (task, day): model.NewBoolVar(f"task {task} --> day {day}")
    for (task, day) in all_possible_allocations
}

# 约束：每个任务必须且只能分配到一个日期
for task in tasks:
    model.Add(sum(allocation[task, day] for day in days) == 1)

# 目标函数：最小化不一致对数量，等价于最大化一致对数量
inconsistent_pairs = []
# 遍历所有i<j的任务对，统计所有可能的不一致情况
for i in range(len(tasks)):
    for j in range(i + 1, len(tasks)):
        # 当任务i分配到day1，任务j分配到day0时，属于不一致对
        inconsistent_pairs.append(allocation[(i, 1)] * allocation[(j, 0)])

# 最小化不一致对的总数
model.Minimize(sum(inconsistent_pairs))

# 求解
solver = cp_model.CpSolver()
status = solver.Solve(model=model)

# 输出结果
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print("最优分配方案：")
    for task in tasks:
        for day in days:
            if solver.Value(allocation[task, day]):
                print(f'Task {task} --> Day {day}')
    # 计算并输出一致对数量
    total_pairs = 3  # C(3,2)=3
    inconsistent_count = solver.Value(sum(inconsistent_pairs))
    print(f"一致对数量：{total_pairs - inconsistent_count}")
elif status == cp_model.INFEASIBLE:
    print("无可行解")

关键说明 #

1. 变量修正：原代码中布尔变量的命名存在笔误，将day {task}修正为day {day}，避免变量名混淆。
2. 目标函数构建：
   • 总任务对数量固定为3（(0,1)、(0,2)、(1,2)），因此最大化一致对数量等价于最小化不一致对数量。
   • 不一致对仅存在一种情况：序号更小的任务分配到更大的日期（day1），序号更大的任务分配到更小的日期（day0）。我们将所有这类情况对应的布尔变量乘积相加，作为需要最小化的目标。
3. 结果验证：最优解的不一致对数量为0，即所有任务对均为一致对，比如所有任务分配到同一日期，或按任务顺序依次分配到day0、day0、day1等。

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