如何用OR-Tools CP-SAT求解器最小化任务分配的任务类型数量？

错误原因分析 #

你之前的代码报错是因为直接将布尔约束表达式（sum(x[...] for task in tasks[type]) >=1）放入求和操作中，OR-Tools不允许直接对约束表达式进行算术运算。这类条件判断必须通过辅助布尔变量做通道（Channeling）转换，将逻辑条件转化为可计算的变量。

实现步骤与代码示例 #

1. 创建辅助布尔变量 #

为每个执行者-任务类型对定义布尔变量y[assignee_idx, type]，用于标记该执行者是否被分配了该类型的至少一个任务：

# 假设assignee_idxs是执行者索引列表，types是任务类型列表
y = {}
for a in assignee_idxs:
    for t in types:
        y[(a, t)] = model.NewBoolVar(f"has_type_{a}_{t}")

2. 添加通道约束关联y与x #

将辅助变量y和任务分配变量x绑定：

• 如果y[a,t]为1，则该执行者至少分配到一个该类型的任务
• 如果y[a,t]为0，则该执行者没有分配到该类型的任务

代码实现：

for a in assignee_idxs:
    for t in types:
        # 获取当前类型下的所有任务索引
        type_tasks = [task for task in task_idxs if tasks[task].type == t]
        if not type_tasks:
            continue  # 跳过无任务的类型
        
        # 约束：y[a,t]为1时，至少有一个该类型任务被分配给a
        model.Add(sum(x[a, task] for task in type_tasks) >= 1).OnlyEnforceIf(y[(a, t)])
        # 约束：y[a,t]为0时，该类型无任务被分配给a
        model.Add(sum(x[a, task] for task in type_tasks) == 0).OnlyEnforceIf(y[(a, t)].Not())

3. 计算每个执行者的任务类型数量 #

为每个执行者创建整数变量type_count[a]，表示其被分配的任务类型总数：

type_count = {}
for a in assignee_idxs:
    type_count[a] = model.NewIntVar(0, len(types), f"type_count_{a}")
    # 约束：type_count[a]等于该执行者对应的y变量之和
    model.Add(type_count[a] == sum(y[(a, t)] for t in types))

4. 整合到目标函数 #

根据你的需求，有两种方式实现最小化类型数量的目标：

方式一：让类型数量接近平均值（类似负载均衡的逻辑）

定义eps_task_types变量，添加约束并将其加入目标函数：

eps_task_types = {}
average_types = len(task_idxs) // len(assignee_idxs)  # 或自定义平均值
for a in assignee_idxs:
    eps_task_types[a] = model.NewIntVar(0, len(types), f"eps_types_{a}")
    model.Add(type_count[a] <= average_types + eps_task_types[a])
    model.Add(type_count[a] >= average_types - eps_task_types[a])

# 多目标最小化：优先平衡负载，再平衡类型数量（可调整权重）
model.Minimize(10 * sum(eps_tasks.values()) + sum(eps_task_types.values()))

方式二：直接最小化类型总数或最大类型数

如果不需要强制接近平均值，直接最小化所有执行者的类型数量总和，或最小化单个执行者的最大类型数：

# 最小化所有执行者的类型数量总和
model.Minimize(sum(type_count.values()))

# 或最小化单个执行者的最大类型数
max_type_count = model.NewIntVar(0, len(types), "max_type_count")
model.AddMaxEquality(max_type_count, type_count.values())
model.Minimize(max_type_count)

完整逻辑整合 #

将上述代码与你已有的负载均衡约束结合，即可同时实现负载均衡和最小化任务类型数量的目标。

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