使用CP-SAT和Python实现约束编程


本文使用 CP-SAT 和 Python 对约束编程 (CP：Constraint Programming ) 进行了实用介绍。以下是要点：

  • 假设您是一家电子商务巨头，想要建造一个新仓库来改善客户服务，但您需要知道最佳仓库位置。
  • 或者您是一家全球运输公司，需要将包裹分配给送货卡车，并且必须选择最佳路线以节省汽油并减少司机加班。
  • 或者一家航空公司希望为新地点提供服务，并且需要知道他们应该使用哪种类型的飞机以及按照什么时间表飞行，以最大限度地提高收入。

上述这类问题被称为离散优化问题。有几种方法可用于解决此类问题。在本文中，我们将讨论其中一种称为约束规划的理论和实践。

声明式范式
约束编程 (CP) 是一种用于解决离散优化问题的声明式范式。这与我们通常习惯的命令式范式形成对比。在命令式编程时，我们描述达到结果所需的步骤。

例如，假设我们想知道给定人员列表中的成年人是谁：

Name    Age
Phil    20
Emma    17
David    11
Thomas    51
Sarah    45
Rebecca    6

典型的命令式方法将解释获得所需结果所需的操作序列：

adult_people = []
for person in people:
    if person.Age >= 18:
        adult_people += person.Name
Phil
Thomas
Sarah

同时，同样的结果也可以声明式地描述为：

SELECT person_name FROM people WHERE age >= 18;
Phil Thomas Sarah


两种方法的结果相同，但过程不同。

  • 在命令式情况下，程序按顺序执行每个步骤以达到结果。
  • 在声明式情况下，程序会获得所需结果的描述（使用语言的可用结构）并自行实现该结果。

约束编程（CP）的基础知识
与上面提到的声明性示例类似，使用 CP：

  • 我们可以描述问题的期望结果：此描述称为模型。

模型的主要组成部分是变量和约束。

  • 变量代表我们要寻找的内容，每个变量都有一个关联的域，即允许此变量采用的一组值。
  • 约束描述变量之间的关系。

CP 中的解决方案是从变量的域中为变量分配值，以满足所有约束。

用三个人凑钱买一块糖果的简单例子来演示 CP 概念，展示如何对变量、域和约束进行建模。：

Alice、Bob 和 Carol 各自有 20 美元，他们想凑钱买一块价值 50 美元的糖果（是的，通货膨胀正在肆虐）。Alice 表示她将至少投入与 Bob 一样多的钱。Carol 只有 5 美元的钞票，所以她的贡献将是 Bob 的倍数。他们中没有人想贡献与其他人完全相同的金额。

这里，我们正在寻找每个人应该为购买糖果贡献的金额。这意味着我们需要每个人一个变量，表示此人应该为购买贡献的金额（a对于 Alice、bBob 和cCarol）。我们首先设置这些变量的域（符号∈表示“in”）：

a ∈ {0, ..., 20}
b ∈ {0, ..., 20}
c ∈ {0, ..., 20}

这些域确保变量的最终值代表捐款者口袋里实际拥有的金额（即最多 20 美元）。

接下来，我们要确保合并后的捐款足以支付糖果的价格，因此我们添加了约束：

a + b + c == 50

Alice 的贡献至少与 Bob 一样多，因此我们将其转化为：

a >= b

Carol 的贡献必须是 5 的倍数：

c % 5 == 0

最后，每个人的贡献金额必须是独一无二的。我们可以使用以下约束来建模：

a != b
a != c
b != c

在这个例子中，我们只有少数几个人，所以这些不平等现象会很好解决。

但如果人数有几百人或几千人呢？事实证明，CP 拥有丰富的表达约束目录，可以封装复杂的概念，称为全局约束。

上述方法的替代方法是使用所谓的alldifferent约束，它确保一组变量都被分配不同的值：
alldifferent(a, b, c)

这样就完成了该问题的模型。您会注意到，我们没有为a、b或c我们自己分配任何值。我们只是定义了三个变量及其域，并使用对这些变量的约束描述了问题的属性。我们的工作完成了。

CP 求解器
解释此模型并返回解决方案的软件称为求解器。求解器的内部工作原理超出了本文的讨论范围，因此出于我们的目的，我们将求解器视为一个黑匣子，它以模型作为输入，并返回有效的解决方案：

a = 19
b = 11
c = 20

返回的解决方案是有效的，因为每个变量都从其域中取一个值，并且所有约束都得到满足。

但是，我们看到 Carol 贡献的金额几乎是 Bob 的两倍。也许存在另一种有效的解决方案，让各方对购买的贡献更加平等？

我们可以为 CP 模型添加一个目标，以尝试实现这一目标。为模型添加目标使我们能够最小化或最大化表达式，而不会损害最终解决方案的有效性（就约束而言）。如果我们能以某种方式最小化最大贡献者的支出金额，这应该会使三项贡献更加接近。那么我们的目标就是找到一个有效的解决方案，使这个值最小：

x ∈ {0, ..., 20}
maximum(x, [a, b, c])
minimize: x

为了实现这一点，我们创建了一个新变量x来表示最大贡献的数额。maximum约束负责从中分配x最大值[a, b, c]。然后目标是最小化x。求解器返回的解决方案现在是：

a = 18
b = 17
c = 15
x = 18

以前，最大捐款额和最小捐款额之间的差额为 9 美元。

根据我们引入的目标，这个差额现在已降至 3 美元，这是最公平的。

现在基本概念已经明确，让我们继续讨论更具挑战性的问题：介绍了一个更复杂的现实世界示例：为拥有多名员工、轮班和角色的商店创建工作时间表。

使用 Python 和 CP-SAT 的实例
让我们利用这些新的 CP 知识来解决一个更复杂的现实世界示例：小型企业的员工排班。
一家商店的老板希望为员工制定每周工作时间表。商店每天营业时间为上午 8 点至晚上 8 点，每天分为三个班次，每个班次 4 小时：早上、下午和晚上。商店中有两个角色：收银员和补货员。

  • 有些员工有资格担任这两个职位，但其他员工只能担任收银员或补货员。
  • 必须始终安排收银员，但补货每天仅需大约 4 小时。因此，对于补货任务，我们每天只需安排一名员工进行一次轮班。这可以是任何轮班，但不能连续安排两个补货轮班。例如，如果在周二晚班安排补货，我们就不能将周三的补货安排在早班。
  • 具备两种职位资格的员工每班次仍只能被分配到一个职位。
  • 员工每天的工作时间不能超过 8 小时，也就是 2 个班次。如果他们一天工作 2 个班次，我们必须确保这些班次之间没有空闲时间 — 例如，我们不能让他们同时工作在同一天的早班和晚班，因为他们在下午班次会有 4 小时空闲时间。

这是问题的基本前提。让我们将其分解为可处理的部分。

空模型
我们首先使用CP-SAT创建一个空模型，CP-SAT 是 Google 作为其[url=https://developers.google.com/optimization]OR-Tools[/url]项目的一部分开发的开源 CP 求解器。

from ortools.sat.python import cp_model model = cp_model.CpModel()

数据
一家商店的老板希望为员工制定每周工作计划。商店每天营业时间为上午 8 点至晚上 8 点，每天分为三个班次，每个班次4 小时：早上、下午和晚上。商店中有两种角色：收银员和补货员。有些员工有资格担任这两种角色，但其他员工只能担任收银员或补货员。

让我们创建一个员工及其胜任职位的列表：

employees = {"Phil": ["Restocker"],
             "Emma": ["Cashier", "Restocker"],
             "David": ["Cashier", "Restocker"],
             "Rebecca": ["Cashier"]}

据说该时间表为期一周，并且我们被告知有三种轮班类型和两种角色：

days = ["Monday",
        "Tuesday",
        "Wednesday",
        "Thursday",
        "Friday",
        "Saturday",
        "Sunday"]

shifts = ["Morning",
          "Afternoon",
          "Evening"]

roles = ["Cashier",
         "Restocker"]


变量
现在，让我们定义我们要寻找的内容。要描述时间表，我们需要参考员工、角色、日期和班次：Emma 是否在周一晚班担任补货员？这可以使用布尔变量来实现。布尔变量是域为 的变量{0, 1}。

schedule = {e:
             {r:
               {d:
                 {s: model.new_bool_var(f"schedule_{e}_{r}_{d}_{s}")
                   for s in shifts}
                 for d in days}
               for r in roles}
             for e in employees}

函数 model.new_bool_var() 创建并返回一个布尔变量，我们将其存储在 schedule 中。在这个结构中，schedule["Emma"]["Restocker"]["Monday"]["Evening"]指的就是其中一个布尔变量。如果 Emma 在周一晚班担任补货员，则该变量等于 1；如果 Emma 在周一晚班不担任补货员，则该变量等于 0。

我们的schedule变量目前不受约束。按照前面提出的问题描述并相应地约束这些变量，我们应该能够得到一个满足店主要求的时间表。

约束条件
让我们来看看问题描述的其余部分，以正确约束计划变量。要在模型中添加新的约束条件，我们只需使用 model.add(...)。

任何时候都必须安排一名收银员。

由于计划表是由布尔变量组成的，因此很容易理解我们如何通过求和这些变量的子集并对这些和施加限制：

for d in days:
    for s in shifts:
        model.add(sum(schedule[e]["Cashier"][d][s] for e in employees) == 1)

补货]可以是任何班次，但两个补货班次不能先后安排。

由于前面的限制，我们已经知道两个补货班次不能在同一天进行。两个补货班次接连安排的唯一方法是，在一天的晚班上安排一个补货班次，在第二天的早班上安排另一个补货班次。通过强制规定每对晚班和早班的补货班次总和不大于 1，我们可以确保这对晚班和早班最多只能安排一次补货班次：

for i in range(len(days)-1):
    model.add(sum(schedule[e]["Restocker"][days[i]]["Evening"] + schedule[e]["Restocker"][days[i+1]]["Morning"] for e in employees) <= 1)

同时具备两种角色资格的员工，每班仍只能被指派担任一种角色。

对于每个员工，所有日班对的所有分配角色总和要么是 1（他们在该日班时段只担任一个角色），要么是 0（他们不在该日班时段工作）：

for e in employees:
    for d in days:
        for s in shifts:
            model.add(sum(schedule[e][r][d][s] for r in roles) <= 1)

有些员工可以胜任这两种角色，但有些员工只能做收银员或补货员。

为了防止员工被分配到不符合条件的角色，我们只需将该员工的角色值匹配为 0（或者换一种说法，我们添加一个约束条件，断言该值为 0）：

for e in employees:
    for r in roles:
        for d in days:
            for s in shifts:
                if r not in employees[e]:
                    model.add(schedule[e][r][d][s] == 0)

员工每天工作时间不能超过 8 小时，即两班倒。如果他们一天工作两班，我们必须确保两班之间没有空闲时间--换句话说，我们不能安排他们在同一天的早班和晚班工作，因为他们在下午班会有 4 个小时的空闲时间。

事实证明，一个约束条件就能同时满足这两个要求：员工既可以上早班，也可以上晚班，或者两班都不上：

for e in employees:
    for d in days:
        model.add(sum(schedule[e][r][d]["Morning"] + schedule[e][r][d]["Evening"] for r in roles) <= 1)

请注意，上述约束不需要指定下午班次的任何内容。如果员工在上午工作，就不能在晚上工作，反之亦然。这样既能确保员工每天最多工作两班，又能确保没有空闲时间，因为只有当员工同时上早班和晚班时才会有空闲时间。

现在问题的建模工作已经完成：

  • 使用布尔变量来表示员工是否在特定角色、班次和日期工作，来对这个问题进行建模。
  • 演示了如何向模型添加各种约束，例如确保收银员始终按时上班、限制工作时间以及满足员工偏好。
  • 它还引入了 CP 中的优化概念，展示了如何最小化分配给员工的最大和最小班次数之间的差异。

本文最后讨论了不同的求解器状态（最佳、不可行、可行、未知）及其在 CP 问题中的含义。

本文介绍为理解和使用 Python 和 CP-SAT 将约束规划应用于实际优化问题奠定了基础。

详细点击标题