了解如何使用 Google OR -tools 设置软约束

Question

我一直在使用 Google OR-tools 并尝试遵循他们的示例来解决调度问题。然而，python 文档有时很难理解，更复杂的例子 ( https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py ) 没有很好地描述。

我希望能够对员工的轮班工作量设置硬限制和软限制。在上面的例子中，我相信这个函数add_soft_sum_constraint()（我已经把它的确切代码放在下面）做了我想做的事情。我想复制它的功能，但我不明白它是如何做到的。

在 2 if 语句中，我不确定delta和excess变量代表什么，以及为什么它们要添加更多约束，而不是仅向 2 个成本列表添加更多约束，这将在稍后最小化目标时使用。

如果有人对此示例有任何见解，我将不胜感激，谢谢。

def add_soft_sum_constraint(model, works, hard_min, soft_min, min_cost,
                        soft_max, hard_max, max_cost, prefix):

cost_variables = []
cost_coefficients = []
sum_var = model.NewIntVar(hard_min, hard_max, '')
# This adds the hard constraints on the sum.
model.Add(sum_var == sum(works))

# Penalize sums below the soft_min target.
if soft_min > hard_min and min_cost > 0:
    delta = model.NewIntVar(-len(works), len(works), '')
    model.Add(delta == soft_min - sum_var)
    # TODO(user): Compare efficiency with only excess >= soft_min - sum_var.
    excess = model.NewIntVar(0, 7, prefix + ': under_sum')
    model.AddMaxEquality(excess, [delta, 0])
    cost_variables.append(excess)
    cost_coefficients.append(min_cost)

# Penalize sums above the soft_max target.
if soft_max < hard_max and max_cost > 0:
    delta = model.NewIntVar(-7, 7, '')
    model.Add(delta == sum_var - soft_max)
    excess = model.NewIntVar(0, 7, prefix + ': over_sum')
    model.AddMaxEquality(excess, [delta, 0])
    cost_variables.append(excess)
    cost_coefficients.append(max_cost)

return cost_variables, cost_coefficients

Answer 1

对于 soft_min：

• delta: 到 soft_min 的距离soft_min - sum_var，如果它是负数，则意味着我们高于 soft_constraint 所以惩罚应该是 0, model.AddMaxEquality(excess, [delta, 0])。

• 过量：我们离 soft_min 有多远，用于丢弃负增量，这就是我们将乘以min_cost。

对于 soft_max：

它几乎相同，但相反。

• delta：到 soft_max 的距离sum_var - soft_max，如果它是负数，则意味着我们低于该 soft_constraint，因此惩罚应为 0，model.AddMaxEquality(excess, [delta, 0])

• 过量：我们离soft_max有多远，用于丢弃负增量，这是我们将乘以 max_cost。

返回：

它返回系数和变量，例如：

假设 soft_min 为 3，min_cost 为 2：

• 如果有人工作 2 天，则超额为 1，成本为 1*2。
• 如果有人工作 1 天，则超额为 2，成本为 2*2。

假设 soft_max 为 5，max_cost 为 3：

• 如果有人工作 6 天，则超额为 1，成本为 1*3。

我们的变量是 [1, 2, 1] 及其系数 [2, 2, 3]。