[OR-Tools]使用 Python CP-SAT 求解器最小化任务“类型”

Question

我正在使用 OR-Tools CP-SAT 求解器使用以下约束生成平衡分配：

model.Add(sum(x[assignee_idx, task] * tasks[task].cost for task in task_idxs) <= average_workload[assignee_idx] + eps_tasks[assignee_idx])

model.Add(sum(x[assignee_idx, task] * tasks[task].cost for task in task_idxs) >= average_workload[assignee_idx] - eps_tasks[assignee_idx])

我正在最小化 eps 项以获得最佳解决方案，分配的任务尽可能接近预期平均值。

现在，此外，我想尽量减少分配给受让人的不同“类型”任务的数量（假设：每个任务都属于一种类型）。

我非常天真地认为像这样的额外约束可以起作用，包括我可以添加到目标术语中的新 eps 术语（仍然最小化）：

model.Add(sum(sum(x[assignee_idx, task] for task in tasks[type]) >= 1 for type in types) <= average_types + eps_task_types)

我已经阅读了有关通道和条件评估的内容，但不知道如何将其应用在这里？ 有人知道如何解决这个问题吗？

（所描述的天真的方法给出了 TypeError: unsupported operand type(s) for +: 'int' and 'BoundedLinearExpression' - 有道理，但该行更多的是在伪代码中概述附加约束的想法是什么）

Answer 1

您需要为每种类型创建 1 个 Bool var。

类似：

types_used = []
for type in types:
  type_used = model.NewBoolVar('')
  types_used.append(type_used)

  # link x with type_used.
  all_x = []
  for task in tasks[type]:
    # if one x is active, the type is used.
    model.AddImplication(x[assignee_idx, task], type_used)
    all_x.append(x[assignee_idx, task])
  # if no x are active, the type_used is false.
  all_x.append(type_used.Not())
  model.AddBoolOr(all_x)

# Constraint the sum of types used.
model.Add(sum(types_used) <= average_types + eps_task_types)

请注意，您可以使用替代代码来实现相反的含义。

  all_negated_x = []
  for task in tasks[type]:
    # if one x is active, the type is used.
    model.AddImplication(x[assignee_idx, task], type_used)
    all_negated_x.append(x[assignee_idx, task].Not())
  # if no x are active, the type_used is false.
  model.AddBoolOr(type_used.Not()).OnlyEnforceIf(all_negated_x)