srcmini本文概述
运筹学和凸优化是应用数学领域, 多年来发现了广泛的商业应用。随着计算能力变得更加负担得起且广泛可用, 研究人员开始构建越来越复杂的优化算法, 以帮助他们做出更好的决策。如今, 由运筹学驱动的应用程序为从全球物流中的路由到能源行业的电力生产平滑提供了所有支持。
随着基础技术变得越来越复杂, 已经创建了一套新的工具来帮助研究人员和开发人员提高工作效率。这些工具(例如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
在define函数中, 你可以按名称请求所需的变量。框架将在变量管理器中定位变量并将其传递到define函数。
实施约束后, 我们可以实现目标。由于这是一个简单的目标, 因此我们将使用ObjectiveComponent：
class ValueObjective(ObjectiveComponent):
def define(self, camera, figurine, cider, horn):
return 5 * camera + 7 * figurine + 2 * cider + 10 * horn
define函数的设置与约束类的define函数非常相似。但是, 我们返回仿射表达式而不是返回约束表达式。
现在已经定义了变量, 约束和目标, 让我们定义模型：
class KnapsackProblem(Problem):
variables = KnapsackVariables
objective = ValueObjective
constraints = [SizeConstraint]
sense = MAXIMIZE
为了构建模型, 我们创建一个类, 该类是Problem类的子类, 并指定变量, 目标, 约束和意义。使用指定的问题, 我们可以解决问题：
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}
你应该看到问题状态, 变量的最终值, 目标值和约束表达式的值。我们还将变量的结果值视为字典。
在那里, 我们有了大约35行的第一个HorusLP问题！
在接下来的示例中, 我们将探索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
并再次运行代码, 你应该在stdout中看到以下内容：
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']
现在, 我们需要实现一个稍微复杂的约束条件-该约束条件确保物品不会同时放入手提箱和行李箱中-也就是说, 如果”手提箱中”变量为1, 则”袋子中”变量需要为零, 反之亦然。当然, 我们要确保允许在两个容器中都不存在该项目的实例。
要添加此约束, 我们需要遍历所有耐用品, 找到”手提箱中”变量和”袋子中”变量, 并断言这些变量的总和小于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如何解决更现实的问题。我们将解决上一篇srcmini文章的后半部分概述的人员配备问题。
为了节省时间, 我们将直接使用该模型的最终版本(有个人冲突, 劳工法规和临时工津贴), 但是初始更简单的模型的实现也可以在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
最后是劳工标准的约束。为了说明的目的, 我们将略微不同地实施此操作：
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)
现在, 我们来设定目标。 dothraki成本和正式员工成本的计算方式大不相同, 因此我们将它们放在单独的目标组成部分中：
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)
]
现在我们可以定义并运行问题：
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()
运行脚本, 你应该看到以下内容：
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
如果将此与我们在上一教程中实现的问题进行比较, 你应该看到结果匹配。
本文总结
祝贺你通过我们的第一个HorusLP教程实现了它！你现在是HorusLP的资深从业人员。
我希望本文使你相信构建MIP模型的好处, 并且希望在以后的项目中使用HorusLP。你可以在GitHub上找到HorusLP源代码以及所有教程的代码。其他HorusLP文档和教程页面将很快添加到GitHub。
由于HorusLP是一个相当新的项目, 我们很乐意听取你的意见并吸收你的意见。如果你有任何疑问, 意见或建议, 请通过srcmini或使用你可以在GitHub上找到的联系信息给我留言。我希望能很快收到你的回信！
评论前必须登录！
注册