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

Question

我一直在使用 Google OR 工具并尝试按照他们的示例来解决调度问题。但是，python 文档有时很难理解，而且更复杂的示例 (https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py) 描述得不好。

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

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

如果有人对这个例子有任何见解，我将不胜感激。

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：

增量：到 soft_min soft_min - sum_var 的距离，如果它是负数，这意味着我们在 soft_constraint 之上，所以惩罚应该是 0，model.AddMaxEquality(excess, [delta, 0]).
过剩：我们距离 soft_min 有多远，用于丢弃负增量，这就是我们将乘以 min_cost.

对于soft_max：

几乎相同但相反。

增量：到 soft_max sum_var - soft_max 的距离，如果它是负数，则表示我们低于 soft_constraint，因此惩罚应为 0，model.AddMaxEquality(excess, [delta, 0])
过剩：我们离 soft_max 有多远，用于丢弃负增量，这就是我们将乘以 max_cost.

Returns:

它returns系数和变量，例如：

假设 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]。

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

Understanding how to set soft constraints using Google OR -tools

python

or-tools

对于soft_min：

对于soft_max：

Returns: