使用 HorusLP 构建优化算法

运筹学和凸优化是应用数学的一个领域，多年来已经发现了广泛的商业应用。 随着计算能力变得更加实惠和广泛可用，研究人员开始构建越来越复杂的优化算法来帮助他们做出更好的决策。 今天，由运筹学提供支持的应用程序支持从全球物流中的路线到能源行业中的电力生产平滑等方方面面。

随着底层技术的复杂性增加，已经创建了一组新工具来帮助研究人员和开发人员更高效地工作。 这些工具（例如 AMPL、CVXPY 和 PuLP）允许开发人员快速定义、构建和运行优化算法，并与各种求解器进行交互。

然而，尽管优化技术和业务需求不断增长，但这些工具中的大多数都或多或少保持不变，并且发展得不够快，无法满足行业需求。 因此，开发、管理、调试和调整这些算法通常需要大量的认知开销，尤其是在快速发展的业务环境中。

今天，我想介绍一下 HorusLP，这是一个有助于算法开发工作流程架构的 Python 优化库。 我们将讨论该工具旨在解决的问题，然后提供 Python 库的快速概述，我们将构建一些示例优化算法。

优化算法开发人员面临的问题

大多数开发人员面临的长期问题之一是构建可维护、高效、惯用的软件和在项目的时间限制内交付产品之间的平衡。 无论您是在开发基于浏览器的应用程序、Web API 还是用户身份验证微服务，通常都需要在实现目标的“正确”方式和“快速”方式之间进行权衡。 随着产品复杂性的增加，这种固有的权衡变得更加突出。

在大多数学科中，开发人员可以通过选择有助于架构的框架或库来缓解这个问题。 在面向 Web 的前端，很多开发者选择 React 或 Angular； 在 API 开发领域，软件工程师可以选择 Django、ASP.NET MVC 或 Play 等。 但是，对于不起眼的优化算法开发人员来说，很少有架构工具可以帮助管理架构复杂性。 开发人员可以自行管理变量、约束和各种目标。 更重要的是，运筹学算法通常难以自省，加剧了问题。

HorusLP 的主要目的是为开发优化算法提供架构框架。 通过提供结构一致性，该框架使组织更容易，并允许开发人员专注于他们最擅长的事情：构建算法。

典型的优化工作流程挑战

开发 OR 算法时有几个主要的复杂性来源：

变量的复杂性

• 通常必须添加变量以适应额外的业务需求，并且没有简单的方法来跟踪它们以用于模型定义和以后的报告。
• 相关变量需要分组和跟踪，并且没有明显的方法来管理它们。

约束的复杂性

• 需要添加和删除约束以支持各种场景并执行调试，但是没有明显的地方可以添加或删除约束。
• 约束通常是相互关联/依赖的，并且没有自然的方式来表达它们的关系。

目标的复杂性

• 如果客观表达式有多个组件，它们可能会变得笨拙。 如果对各个组件进行加权，则可能会加剧这种情况，并且需要根据业务需求调整权重。

调试的复杂性

• 在开发过程中没有简单的方法来查看模型的结果。 开发人员必须显式打印新变量和约束值才能看到结果。 这会导致重复的代码和较慢的开发。
• 当添加约束导致模型变得不可行时，约束导致模型变得不可行的原因可能并不明显。 通常，开发人员必须通过反复试验来排除各种约束并寻找不兼容的地方

HorusLP 希望通过提供结构、工具和最佳实践来提高开发人员的生产力和产品的可维护性，从而使这些挑战更易于管理。

HorusLP 教程：优化算法和 API 概述

事不宜迟，让我们深入了解 HorusLP 库可以为您做什么！

由于 HorusLP 基于 Python 和 PuLP，我们将希望使用 pip 安装它们。 在命令行中运行以下命令：

 Pip install horuslp pulp

安装完成后，让我们继续打开一个 Python 文件。 我们将实现我之前关于运筹学的文章中的背包问题。

HorusLP 库有一个非常简单的声明式 API 和很少的样板文件。 让我们从导入必要的类和变量开始：

 from horuslp.core.Variables import BinaryVariable # we will be using binary variables, so we will import the BinaryVariable class from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent # We will also need to import the constraint class, variable manager class, the main problem class, and the objective class to define the objective. from horuslp.core.constants import MAXIMIZE # since we're maximizing the resulting value, we want to import this constant

导入所有变量后，让我们定义此问题所需的变量。 我们通过创建一个变量管理器子类并用二进制变量填充它来做到这一点：

 class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), # the first argument is the name of the variable BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') ]

现在定义了变量，让我们定义约束。 我们通过子类化主约束类并实现其“定义”功能来创建约束。

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

在定义函数中，您可以按名称询问所需的变量。 框架将在变量管理器中定位变量并将其传递给定义函数。

约束实现后，我们就可以实现目标了。 由于它是一个简单的目标，我们将使用ObjectiveComponent ：

 class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

定义函数的设置与约束类的定义函数非常相似。 然而，我们不是返回一个约束表达式，而是返回一个仿射表达式。

现在已经定义了变量、约束和目标，让我们定义模型：

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE

为了构建模型，我们创建一个作为问题类的子类的类，并指定变量、目标、约束和意义。 指定问题后，我们可以解决问题：

 prob = KnapsackProblem() prob.solve()

求解后，我们可以使用问题类的print_results函数打印结果。 我们还可以通过查看result_variables类来访问特定变量的值。

 prob.print_results() print(prob.result_variables)

运行脚本，您应该会看到以下输出：

 KnapsackProblem: Optimal camera 0.0 figurine 1.0 cider 0.0 horn 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'camera': 0.0, 'figurine': 1.0, 'cider': 0.0, 'horn': 1.0}

您应该看到问题状态、变量的最终值、目标值和约束表达式的值。 我们还将变量的结果值视为字典。

我们有了它，我们的第一个 HorusLP 问题大约 35 行！

在接下来的示例中，我们将探索 HorusLP 库的一些更复杂的功能。

使用变量组

有时，变量是相关的并且属于一个逻辑组。 在背包问题的情况下，所有变量都可以放入一个对象组中。 我们可以重构代码以使用变量组。 确保保存上一节中的代码，因为我们将在后续教程中引用它！

像这样更改导入语句：

 from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp.core.constants import MAXIMIZE

现在我们还需要像这样更改背包变量声明：

 class KnapsackVariables(VariableManager): vars = [ BinaryVariableGroup('objects', [ 'camera', 'figurine', 'cider', 'horn' ]) ]

第一个参数是变量组的名称，第二个变量是该组中变量的名称列表。

现在我们需要更改约束和目标定义。 我们不会要求单独的名称，而是要求变量组，它将作为字典传递，其中键是名称，值是变量。 像这样更改约束和目标定义：

 class SizeConstraint(Constraint): def define(self, objects): return 2 * objects['camera'] + 4 * objects['figurine'] + 7 * objects['cider'] + 10 * objects['horn'] <= 15 class ValueObjective(ObjectiveComponent): def define(self, objects): return 5 * objects['camera'] + 7 * objects['figurine'] + 2 * objects['cider'] + 10 * objects['horn']

现在我们可以使用相同的问题定义并运行命令：

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results() print(prob.result_variables)

您应该在输出中看到这一点：

 KnapsackProblem: Optimal objects[camera] 0.0 objects[figurine] 1.0 objects[cider] 0.0 objects[horn] 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'objects': {'camera': 0.0, 'figuring': 1.0, 'cider': 0.0, 'horn': 1.0}}

管理多个约束

具有单一约束的模型相对较少。 处理多个约束时，最好将所有约束放在一个位置，以便轻松跟踪和管理它们。 HorusLP 让这一切变得自然。

例如，假设我们想看看如果我们强制模型在我们的背包中添加一个摄像头，结果会如何变化。 我们将实施一个额外的约束并将其添加到我们的问题定义中。

回到我们在第一个教程中实现的模型。 添加以下约束：

 class MustHaveItemConstraint(Constraint): def define(self, camera): return camera >= 1

要将约束添加到模型中，我们只需将其添加到问题定义中，如下所示：

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, MustHaveItemConstraint # just add this line :) ] sense = MAXIMIZE

运行问题，您应该会看到以下输出：

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

您应该会在标准输出中看到打印的新约束，以及更改后的最佳变量值。

管理依赖约束和约束组

约束通常彼此相关，或者因为它们相互依赖，或者因为它们在逻辑上属于同一组。

例如，如果要设置约束来限制一组变量的绝对值之和，则必须首先指定约束来表达预期变量之间的绝对值关系，然后再指定绝对值限制。 有时，您需要对一组变量应用类似的约束，以表达变量之间的特定关系。

为了表达这些分组，我们可以使用约束定义的依赖约束特征。 要查看如何使用依赖约束功能，请重构上一个问题的SizeConstraint ，如下所示：

 class SizeConstraint(Constraint): dependent_constraints = [MustHaveItemConstraint] def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

现在为了测试依赖约束是否自动实现，让我们将MustHaveItemConstraint排除在问题定义之外：

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, ] sense = MAXIMIZE

再次运行代码，您应该会在标准输出中看到以下内容：

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

看起来MustHaveItemConstraint已实现！ 有关如何使用依赖约束的更复杂示例，请参阅教程末尾的人员配备示例。

管理多个加权目标

通常，在我们的优化算法的开发过程中，我们会遇到一个由多个部分组成的客观表达式。 作为我们实验的一部分，我们可能会改变各种目标成分的权重，以使算法偏向于期望的结果。 CombinedObjective提供了一种简洁明了的方式来表达这一点。

假设我们想让算法偏向于选择小雕像和苹果酒。 让我们重构上一节中的代码以使用CombinedObjective 。

首先，像这样导入CombinedObjective类：

 from horuslp.core import CombinedObjective

我们可以像这样实现一个独立的目标组件：

 class ILoveCiderFigurineObjectiveComponent(ObjectiveComponent): def define(self, figurine, cider): return figurine + cider

现在我们可以通过实现一个CombinedObjective来组合价值目标和苹果酒/雕像目标：

 class Combined(CombinedObjective): objectives = [ (ILoveCiderFigurineObjectiveComponent, 2), # first argument is the objective, second argument is the weight (ValueObjectiveComponent, 1) ]

现在让我们像这样更改问题定义：

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = Combined constraints = [SizeConstraint] sense = MAXIMIZE

运行问题，您应该会看到以下输出：

 KnapsackProblem: Optimal camera 1.0 figurine 1.0 cider 1.0 horn 0.0 Combined: 18.00 ILoveCiderFigurineObjectiveComponent: 2.00 * 2 ValueObjectiveComponent: 14.00 * 1 SizeConstraint: 13.00 MustHaveItemConstraint: 1.00

输出将概述组合的目标值、每个目标组件的值、权重，当然还有所有约束的值。

寻找不兼容的约束

在开发算法时，我们经常会遇到不可行的模型。 如果模型很复杂，确定模型突然不可行的原因可能具有挑战性。 在这些情况下，HorusLP 有一个方便的工具可以帮助您。

假设我们正在添加约束并最终得到以下一组约束：

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 class SizeConstraint2(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 20 class MustHaveItemConstraint(Constraint): def define(self, cider): return cider >= 1 class IncompatibleConstraint1(Constraint): def define(self, camera): return camera >= 1 class IncompatibleConstraint2(Constraint): def define(self, camera): return camera <= 0

我们对背包中物品的总大小有几个限制条件，一个要求苹果酒必须放在背包里的约束条件，还有一组不兼容的约束条件，要求相机既在背包里又不在背包里。 （当然，在现实世界的算法中，约束通常不那么明显，并且涉及复杂的变量关系和约束。）

还假设约束按以下方式分组，可能会使检测更加困难：

 class CombinedConstraints1(Constraint): dependent_constraints = [SizeConstraint2, IncompatibleConstraint1] class CombinedConstraints2(Constraint): dependent_constraints = [SizeConstraint, IncompatibleConstraint2] # MustHaveItemConstraint will be included in the problem definition independently

这是问题定义：

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [CombinedConstraints1, CombinedConstraints2, MustHaveItemConstraint] sense = MAXIMIZE

运行问题，你应该会看到以下结果：

 KnapsackProblem: Infeasible

不好了！ 我们做什么？ 如果我们使用大多数工具，我们必须开始一个困难的调试会话，在其中我们一一缩小潜在的冲突约束。 幸运的是，HorusLP 具有不兼容搜索功能，可以帮助您更快地缩小不兼容约束。 使用不兼容搜索功能的最简单方法是更改print_results调用：

 prob.print_results(find_infeasible=True)

就那么简单！ 运行代码，现在您应该看到以下输出：

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('CombinedConstraints1', 'CombinedConstraints2')

伟大的！ 现在我们已经确定MustHaveItemConstraint不是不可行的原因，问题是由于CombinedConstraints1和CombinedConstraints2造成的。

这给了我们一些信息，但是在组合约束之间有四个依赖约束。 我们能否确定这四个约束中的哪一个是不相容的？ 嗯，是。 因此修改您的print_results调用：

 prob.print_results(find_infeasible=True, deep_infeasibility_search=True)

这将使不可行搜索扩展相关约束，以便我们更详细地了解导致不可行的原因。 运行它，您应该会看到以下输出：

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('IncompatibleConstraint1', 'IncompatibleConstraint2')

虽然每次都运行深度不可行性搜索很诱人，但对于具有大量总约束的实际问题，深度不可行性搜索可能会变得非常资源密集和耗时。 因此，最好运行基本不可行搜索以缩小可能性，并在进行一些手动调查后对较小的子集运行深度不可行搜索。

从数据文件构建算法

在构建模型时，我们很少有机会对每个约束和变量进行硬编码。 通常，我们的程序必须足够灵活，才能根据输入数据更改模型。 假设我们想从以下 JSON 构建我们的背包问题，而不是硬编码输入：

 { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 }

我们可以依靠 kwargs 对我们为约束和目标实现的“定义”函数的支持来做到这一点。

让我们从简单的背包问题（我们在教程第 1 节中实现的问题）修改代码。 首先，让我们将 JSON 字符串放入文件中。 当然，我们通常会从外部源读取它，但为了简单起见，我们将所有内容保存在一个文件中。 将以下内容添加到您的代码中：

 JSON = ''' { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 } '''

我们还要确保我们的程序能够解析它。 将以下内容添加到您的导入语句中：

 Import json

现在，让我们修改我们的变量设置代码：

 mip_cfg = json.loads(JSON) class KnapsackVariables(VariableManager): vars = [ BinaryVariable(i['name']) for i in mip_cfg['items'] ]

这将为 JSON 中的每个项目定义一个变量，并为其命名。

让我们像这样更改约束和目标定义：

 class CapacityConstraint(Constraint): def define(self, **kwargs): item_dict = {i['name']: i['weight'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs) <= mip_cfg['capacity'] class ValueObjective(ObjectiveComponent): def define(self, **kwargs): item_dict = {i['name']: i['value'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs)

通过请求**kwargs而不是特定的变量， define函数得到一个包含所有变量名的字典。 然后约束定义函数可以访问字典中的变量。

注意：对于变量组，它将是一个嵌套字典，其中第一级是组名，第二级是变量名。

其余的很简单：

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

运行此程序，您应该会看到以下输出：

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00

在 HorusLP 中定义自定义指标

有时，出于调试和报告的目的，我们将构建不直接在目标中表达或作为约束的自定义指标。 HorusLP 具有使指定自定义指标变得简单的功能。

假设我们想要跟踪上一节中的模型放入背包中的水果数量。 为了跟踪这一点，我们可以定义一个自定义指标。 让我们从导入 Metrics 基类开始：

 From horuslp.core import Metric

现在让我们定义自定义指标：

 class NumFruits(Metric): name = "Number of Fruits" def define(self, apple, banana): return apple + banana

如您所见，定义的接口看起来与约束和目标组件类的接口非常相似。 如果到目前为止您已经按照本教程进行操作，那么您应该对此非常熟悉。

现在我们需要将度量添加到问题定义中。 这里的接口再次与约束定义非常相似：

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective metrics = [NumFruits] sense = MAXIMIZE

运行它，您应该会看到以下输出：

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00 Number of Fruits: 1.00

您可以在底部看到打印的水果数量。

解决更复杂的问题：两个背包

让我们看一个稍微复杂一点的例子。 假设我们有一个包和一个手提箱，而不是一个背包。 我们还有两类对象，耐用的和易碎的。 手提箱更具保护性，可以装易碎和耐用的物品。 另一方面，袋子只能装耐用品。 还假设项目的数据在以下 JSON 中给出：

 { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 }

让我们看看这如何改变模型。 让我们从一张白纸开始，因为模型会完全不同。 从问题的设置开始：

 import json from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, Metric, ObjectiveComponent from horuslp.core.constants import MAXIMIZE JSON = ''' { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 } ''' mip_cfg = json.loads(JSON)

现在让我们设置变量。 我们将为每个可能的项目/容器组合设置一个二进制变量。

 class KnapsackVariables(VariableManager): vars = [ # suitcase can hold both fragile and durable goods BinaryVariableGroup('suitcase_f', [i['name'] for i in mip_cfg['fragile']]), BinaryVariableGroup('suitcase_d', [i['name'] for i in mip_cfg['durable']]), # bag can only hold durable goods. BinaryVariableGroup('bag_d', [i['name'] for i in mip_cfg['durable']]) ]

现在我们要为手提箱和包实现重量约束。

 class SuitcaseCapacityConstraint(Constraint): def define(self, suitcase_d, suitcase_f): fragile_weight = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_weight = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_weight + durable_weight <= mip_cfg['suitcase_capacity'] class BagCapacityConstraint(Constraint): def define(self, bag_d): durable_weight = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return durable_weight <= mip_cfg['bag_capacity']

现在我们需要实现一个稍微复杂一点的约束——确保一个物品不会同时进入手提箱和包的约束——也就是说，如果“in the suitcase”变量是 1，那么“in the bag”变量必须为零，反之亦然。 当然，我们要确保允许项目最终不在两个容器中的实例。

要添加此约束，我们需要遍历所有耐用物品，找到“in the suitcase”变量和“in the bag”变量，并断言这些变量的总和小于 1。

我们可以在 HorusLP 中很容易地动态定义依赖约束：

 class UniquenessConstraints(Constraint): def __init__(self): super(UniquenessConstraints, self).__init__() # call the dependent constraint builder function for every durable item, and push them into dependent constraints. dependent_constraints = [self.define_uniqueness_constraint(item) for item in mip_cfg['durable']] self.dependent_constraints = dependent_constraints def define_uniqueness_constraint(self, item): # classes are first-class objects in python, so we can define a class within this function and return it class UQConstraint(Constraint): # we name the constraint based on the item this is for, so that debugging is easier. name = "Uniqueness_%s" % item['name'] def define(self, suitcase_d, bag_d): # the define function can access the variables much in the same way as other functions return suitcase_d[item['name']] + bag_d[item['name']] <= 1 return UQConstraint

现在定义了约束，让我们构建目标。 目标很简单，就是我们从容器中的所有项目中获得的所有值的总和。 因此：

 class TotalValueObjective(ObjectiveComponent): def define(self, suitcase_f, suitcase_d, bag_d): fragile_value = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_value_s = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) durable_value_d = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_value + durable_value_s + durable_value_d

让我们还定义一些自定义指标，以便我们可以一目了然地看到袋子和手提箱中放入了多少重量，以及手提箱重量中有多少来自耐用品和易碎品：

 class SuitcaseFragileWeightMetric(Metric): def define(self, suitcase_f): return sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) class SuitcaseDurableWeightMetric(Metric): def define(self, suitcase_d): return sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) class BagWeightMetric(Metric): def define(self, bag_d): return sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])

现在我们已经完成了所有部分，让我们实例化问题并运行模型：

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [SuitcaseCapacityConstraint, BagCapacityConstraint, UniquenessConstraints] objective = TotalValueObjective metrics = [SuitcaseDurableValueMetric, SuitcaseFragileValueMetric, BagValueMetric] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

运行它，您应该在标准输出中看到以下输出：

 KnapsackProblem: Optimal suitcase_f[camera] 1.0 suitcase_f[glasses] 1.0 suitcase_f[apple] 1.0 suitcase_f[pear] 0.0 suitcase_f[banana] 1.0 suitcase_d[figurine] 0.0 suitcase_d[horn] 0.0 suitcase_d[leatherman] 0.0 bag_d[figurine] 1.0 bag_d[horn] 1.0 bag_d[leatherman] 1.0 TotalValueObjective: 32.00 SuitcaseCapacityConstraint: 15.00 BagCapacityConstraint: 17.00 Uniqueness_figurine: 1.00 Uniqueness_horn: 1.00 Uniqueness_leatherman: 1.00 SuitcaseDurableWeightMetric: 0.00 SuitcaseFragileWeightMetric: 15.00 BagWeightMetric: 17.00

所以相机、眼镜、苹果和香蕉放入手提箱的重量为 15 个单位，小雕像、喇叭和皮革人都放入包中，总共有 17 个重量单位。 货物的总价值为 32 个价值单位。 有趣的是，行李箱中没有一件耐用品，很可能是因为袋子有足够的容量容纳所有耐用品。

一个更大更现实的场景：人员配备问题

如果您在我们的 HorusLP 教程中做到了这一点，那么恭喜！ 您现在对如何使用 HorusLP 有了很好的了解。

然而，到目前为止，我们一直在研究的所有示例都是背包问题的排列，并且一些要求和参数有点不切实际。 让我们一起解决一个问题，看看 HorusLP 如何解决更现实的问题。 我们将解决我之前的 Toptal 文章后半部分中概述的人员配备问题。

出于时间考虑，我们将直接进入模型的最终版本（包括个人冲突、劳动法规和临时工津贴），但初始更简单模型的实现也可以在 GitHub 上找到。

因此，让我们从设置问题开始：

 from horuslp.core.Variables import BinaryVariableGroup, IntegerVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent, CombinedObjective from horuslp.core.constants import MINIMIZE shift_requirements = [1, 4, 3, 5, 2] # the number of workers we need to staff for each shift # the availability and pay rates of each of the employees workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } } # the following people can't work together, sadly. ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } # Dothraki Staffing Corp will provide us with expensive temp workers DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

现在让我们定义变量，在这种情况下，这些变量是确定工人是否应该轮班工作的二进制变量，以及确定每个轮班雇用多少 dothrakis 的整数变量：

 class StaffingVariables(VariableManager): vars = [] def __init__(self): # like dependent constraints, we can dynamically define variables in the init function super(StaffingVariables, self).__init__() # regular workers varkeys = [] for employee, availability_info in workers.items(): for shift in availability_info['availability']: varkeys.append((employee, shift)) self.vars.append(BinaryVariableGroup('employee_shifts', varkeys)) # dothrakis dothraki_keys = [i for i in range(len(shift_requirements))] self.vars.append(IntegerVariableGroup('dothraki_workers', dothraki_keys, 0, DOTHRAKI_COST))

现在让我们实施要求我们为每个班次配备足够人员的约束：

 class SufficientStaffingConstraint(Constraint): # we need to staff people sufficiently dependent_constraints = [] def __init__(self): super(SufficientStaffingConstraint, self).__init__() for shift_num, shift_req in enumerate(shift_requirements): self.dependent_constraints.append(self.build_shift_constraint(shift_num, shift_req)) def build_shift_constraint(self, sn, sr): class ShiftConstraint(Constraint): name = "shift_requirement_%d" % sn def define(self, employee_shifts, dothraki_workers): variables = [val for key, val in employee_shifts.items() if key[1] == sn] variables.append(dothraki_workers[sn]) return sum(variables) >= sr return ShiftConstraint

现在，我们需要实施阻止特定人员相互合作的约束：

 class PersonalConflictsConstraint(Constraint): # some people can't work together dependent_constraints = [] def __init__(self): super(PersonalConflictsConstraint, self).__init__() for person_1, person_2 in ban_list: for shift in range(len(shift_requirements)): self.dependent_constraints.append(self.build_conflict_constraint(person_1, person_2, shift)) def build_conflict_constraint(self, p1, p2, s): class ConflictConstraint(Constraint): name = "Conflict_%s_%s_%d" % (p1, p2, s) def define(self, employee_shifts): if (p1, s) in employee_shifts and (p2, s) in employee_shifts: return employee_shifts[p1, s] + employee_shifts[p2, s] <= 1 return True # returning true will make the constraint do nothing return ConflictConstraint

And finally the labor standards constraint. We'll implement this one slightly differently for demonstrative purposes:

 class LaborStandardsConstraint(Constraint): # we can make someone work more than two shifts a day. dependent_constraints = [] def __init__(self): super(LaborStandardsConstraint, self).__init__() for worker in workers.keys(): # we don't need a constraint builder function, but in those circumstances # we need to set the needed values as class variables and refer to them # via the self keyword due to how python's closure system works class LaborConstraint(Constraint): # we can't use worker directly! wk = worker name = "labor_standard_%s" % worker def define(self, employee_shifts): # we need to access the worker using self. Change self.wk to worker to see # why we need to do this worker_vars = [var for key, var in employee_shifts.items() if key[0] == self.wk] return sum(worker_vars) <= 2 self.dependent_constraints.append(LaborConstraint)

And now let's set up the objectives. The dothraki cost and regular employee costs are calculated very differently, so we'll put them in separate objective components:

 class CostObjective(ObjectiveComponent): # this is the cost function for all the named workers def define(self, employee_shifts, dothraki_workers): costs = [ workers[key[0]]['cost'] * var for key, var in employee_shifts.items() ] return sum(costs) class DothrakiCostObjective(ObjectiveComponent): # don't forget the Dothrakis def define(self, dothraki_workers): dothraki_costs = [ dothraki_workers[sn] * DOTHRAKI_COST for sn in dothraki_workers ] return sum(dothraki_costs) class TotalCostObjective(CombinedObjective): objectives = [ (CostObjective, 1), (DothrakiCostObjective, 1) ]

And now we can define and run the problem:

 class StaffingProblem(Problem): variables = StaffingVariables objective = TotalCostObjective constraints = [SufficientStaffingConstraint, PersonalConflictsConstraint, LaborStandardsConstraint] sense = MINIMIZE # we're minimizing this time, not maximizing. if __name__ == '__main__': prob = StaffingProblem() prob.solve() prob.print_results()

Run the script and you should see the following:

 StaffingProblem: Optimal employee_shifts[('Melisandre', 0)] 0.0 employee_shifts[('Melisandre', 1)] 1.0 employee_shifts[('Melisandre', 4)] 1.0 employee_shifts[('Bran', 1)] 0.0 employee_shifts[('Bran', 2)] 1.0 employee_shifts[('Bran', 3)] 1.0 employee_shifts[('Bran', 4)] 0.0 employee_shifts[('Cersei', 2)] 0.0 employee_shifts[('Cersei', 3)] 0.0 employee_shifts[('Daenerys', 3)] 1.0 employee_shifts[('Daenerys', 4)] 0.0 employee_shifts[('Theon', 1)] 1.0 employee_shifts[('Theon', 3)] 1.0 employee_shifts[('Theon', 4)] 0.0 employee_shifts[('Jon', 0)] 0.0 employee_shifts[('Jon', 2)] 1.0 employee_shifts[('Jon', 4)] 0.0 employee_shifts[('Tyrion', 1)] 1.0 employee_shifts[('Tyrion', 3)] 1.0 employee_shifts[('Tyrion', 4)] 0.0 employee_shifts[('Jaime', 1)] 1.0 employee_shifts[('Jaime', 2)] 0.0 employee_shifts[('Jaime', 4)] 1.0 employee_shifts[('Arya', 0)] 1.0 employee_shifts[('Arya', 1)] 0.0 employee_shifts[('Arya', 3)] 1.0 dothraki_workers[0] 0.0 dothraki_workers[1] 0.0 dothraki_workers[2] 1.0 dothraki_workers[3] 0.0 dothraki_workers[4] 0.0 TotalCostObjective: 335.00 CostObjective: 290.00 * 1 DothrakiCostObjective: 45.00 * 1 shift_requirement_0: 1.00 shift_requirement_1: 4.00 shift_requirement_2: 3.00 shift_requirement_3: 5.00 shift_requirement_4: 2.00 Conflict_Jon_Cersei_2: 1.00 Conflict_Jon_Jaime_2: 1.00 Conflict_Jon_Jaime_4: 1.00 Conflict_Daenerys_Cersei_3: 1.00 Conflict_Daenerys_Jaime_4: 1.00 Conflict_Arya_Jaime_1: 1.00 Conflict_Arya_Cersei_3: 1.00 Conflict_Arya_Melisandre_0: 1.00 Conflict_Arya_Melisandre_1: 1.00 Conflict_Jaime_Cersei_2: 0.00 labor_standard_Melisandre: 2.00 labor_standard_Bran: 2.00 labor_standard_Cersei: 0.00 labor_standard_Daenerys: 1.00 labor_standard_Theon: 2.00 labor_standard_Jon: 1.00 labor_standard_Tyrion: 2.00 labor_standard_Jaime: 2.00 labor_standard_Arya: 2.00

If you compare this with the problem we implemented in the previous tutorial, you should see that the results match.

包起来

Congratulations for making it through our first HorusLP tutorial! You're now a competent practitioner of HorusLP.

I hope that this article convinced you of the benefits of architecting your MIP models, and that you will make use of HorusLP in your coming projects. You can find the HorusLP source code, as well as the code for all the tutorials, on GitHub. Additional HorusLP documentation and a tutorial page will be added to GitHub very soon.

As HorusLP is a fairly new project, we would love to hear from you and incorporate your input. If you have any questions, comments, or suggestions, please drop me a line either through Toptal or using the contact information you can find on GitHub. I hope to hear from you soon!