HorusLP-Gurobi：Gurobi 的高级优化架构

已发表: 2022-03-11

随着优化技术变得越来越复杂，商业求解器已开始在行业中发挥越来越重要的作用。 与开源求解器相比，商业解决方案往往具有更多用于求解复杂优化模型的功能，例如高级预求解、热启动和分布式求解。

市场上最受欢迎的商业求解器之一是 Gurobi，以联合创始人顾宗浩、爱德华·罗斯伯格和罗伯特·比克斯比的名字命名，他们都是商业求解器领域的先驱。 Gurobi 在近期历史上为许多备受瞩目的优化项目提供了支持，包括 FCC 的带宽分配项目和宾夕法尼亚州监狱的囚犯重新分配项目。

今天，我们将看看 HorusLP，一个为优化建模提供高级声明接口的软件包，如何与 Gurobi 的 API 集成，在利用 Gurobi 最先进的功能的同时为用户带来直观的建模体验。

优化：快速复习

对于那些不熟悉优化或运筹学的人来说，优化是指一组数学技术，可以在受约束系统约束的方程组中找到变量的最佳值。 如果上面的句子听起来有点枯燥，也许一个例子可以帮助说明。

假设你有一个承载能力为 15 磅的背包。 您面前有几件物品，每件都有特定的重量和货币价值：

  1. 相机：重量 2 磅，价值 5 美元
  2. 公仔：重 4 磅，价值 7 美元
  3. 苹果酒：重 7 磅，价值 2 美元
  4. 号角：重 10 磅，价值 10 美元。

您想选择放入背包的物品，以使总重量保持在 15 磅以下，但价值最大化。 （如果您需要更多关于我们为何将高价值物品放入背包的背景信息，我们鼓励您利用您的想象力进行叙述。好的候选叙述包括从火灾和房地产拍卖中抢救物品……或我们的一些邪恶活动宁可不提。）

我们可以将问题表述为以下优化问题：

 Let // Each variable stands for whether we put the item into the knapsack Camera = {0, 1} Figurine = {0, 1} Cider = {0, 1} Horn = {0, 1} // Maximize dollar value Maximize 5 * camera + 7 * figurine + 2 * cider + 10 * horn // Weight must stay below 15 pounds 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

一旦我们制定了这个问题，我们就可以应用优化技术来找到最好的物品放入我们的背包。 您可以从我之前关于使用 Python 解决优化问题和使用核心 HorusLP API 解决优化问题的文章中找到解决方案的示例。

底层的数学技术非常吸引人，但超出了本文的范围。 如果您想了解更多信息，我建议您查看此处和此处，均由 Gurobi 提供。

古罗比

虽然最早的优化问题是由使用计算器的数学家团队解决的，但今天大多数优化问题都是使用称为求解器的专用软件解决的。 虽然大多数求解器通常能够找到大多数公式化的线性和整数规划问题的解，但一些求解器比其他求解器更有能力。 他们可以解决其他人无法解决的问题类别，通过应用尖端数学更快地解决问题，或使用分布式计算机解决大型困难问题。 最先进的功能通常由专门构建最快、最复杂求解器的公司开发和维护的商业求解器提供。

Gurobi 是商业求解器市场的领导者之一，被优化社区的大部分人使用，包括政府、学术机构和从金融到物流等行业的公司。 在速度方面，gurobi 在用于判断商业和开源求解器的几个基准测试中始终表现出色。

Gurobi 还附带了一个强大的 Python API，允许您从 Python 构建模型。 此功能使建模者可以在模型构建期间访问所有 Python 有用的数据操作库，这极大地帮助了他们的过程。 作为 gurobi Python API 的演示，您可以通过以下方式对背包问题进行建模：

 import gurobipy as gr m = gr.Model() camera = m.addVar(name='camera', vtype=gr.GRB.BINARY) figurine = m.addVar(name='figurine', vtype=gr.GRB.BINARY) cider = m.addVar(name='cider', vtype=gr.GRB.BINARY) horn = m.addVar(name='horn', vtype=gr.GRB.BINARY) m.addConstr(2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 , 'size constraint') m.setObjective(5 * camera + 7 * figurine + 2 * cider + 10 * horn, gr.GRB.MAXIMIZE) m.optimize() print(camera.x) print(figurine.x) print(horn.x) print(cider.x)

运行该示例将为您提供以下输出：

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% -0.0 1.0 1.0 -0.0

荷鲁斯LP

HorusLP 是一个基于优化算法开发经验的优化建模库。 当前可用的建模库缺乏处理运筹学商业应用通常遇到的复杂、多方面问题所需的工具。

虽然大多数优化库都提供低级命令式接口，但随着优化模型变得越来越复杂，需要更好的工具来管理复杂性。 HorusLP 是一个库，它提供了更高级的工具来管理这些复杂性。 HorusLP 还提供了强大的调试和报告工具，可以加快开发和迭代。

HorusLP 的核心是一个面向对象的库，它围绕优化模型提供急需的架构。 通过利用 Python 面向对象的语法，HorusLP 库提供了一个可以优化优化模型的结构。 结果是一个解耦、模块化且易于阅读的代码库。

如果您想通过代码示例更详细地介绍核心 HorusLP 库，您可以在此处找到教程。

HorusLP-Gurobi 集成

虽然 HorusLP 的核心 API 为构建优化模型提供了方便的高级 API，但它是基于 PuLP 构建的，虽然能够使用 Gurobi 作为求解器，但无法访问 Gurobi 的一些更高级的功能。

HorusLP-Gurobi 是使用 Gurobi 的 Python API 构建的 HorusLP API 版本。 这允许用户直接访问 Gurobi 的高级功能，同时保持 HorusLP API 的一致性。

指导 HorusLP-Gurobi 开发的关键理念之一是与 HorusLP 核心 API 保持一致。 通过保持 HorusLP 的简约结构一致，开源求解器的用户可以通过安装 Gurobi API 并切换导入语句轻松过渡到使用 Gurobi。

对于简单的模型，基于 HorusLP 的模型将需要更多的代码行，而不是简单地使用 Python API。 然而，随着开发过程的继续以及模型变得越来越复杂，HorusLP API 的面向对象和声明式设计将便于调试和开发。 面向对象也将使模型更具可读性，因为模型定义创建集中并清楚地描述了目标、约束和变量等。

事不宜迟，让我们深入研究一些代码示例！

代码示例

基本 HorusLP API

因为 HorusLP-Gurobi 保持 API 一致，所以 HorusLP 核心教程中的代码可以通过对导入的简单更改来移植。 但是，要使用 HoruLP-Gurobi，您需要确保已安装 Gurobi 优化器和 Gurobi 的 Python 接口。 您可以通过在此处与他们联系来获得 Gurobi。

安装 Gurobi 后，我们可以开始使用 HorusLP-Gurobi 进行编码！ 让我们从安装必要的包开始：

 Pip install horuslp horuslp-gurobi

安装完成后，我们就可以开始使用 HorusLP-Gurobi 了！ 回想一下前面的示例背包问题。 我们可以使用 HorusLP-Gurobi 对问题进行建模，如下所示：

首先，导入相关库。

 from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE

定义一些变量。

 class KnapsackVariables(VariableManager): # we define variables by declaring the “vars” class variable vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn')

现在，我们可以使用约束类定义约束。

 class SizeConstraint(Constraint): # implement the 'define' function, the variables will get passed in by name def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

然后我们可以以类似的方式实现目标。

 class ValueObjective(ObjectiveComponent): # implement the define function and return the objective expression def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

最后，我们可以定义问题。

 class KnapsackProblem(Problem): # defining a problem using the Horus API is a matter of setting variables in the subclass variables = KnapsackVariables objective = ValueObjective # constraints is a list variable, since there can be multiple constraints,. constraints = [SizeConstraint] # make sure to set the sense! sense = MAXIMIZE

我们实例化问题并调用求解函数。 这就是魔法发生的地方。

 prob = KnapsackProblem() # instantiate prob.solve() # call the solve method prob.print_results() # optional: print the standard Horus debug report print(prob.result_variables) # optional: print the variable results as a list

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

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% 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}

第一部分是 Gurobi 求解器，第二部分是 HorusLP 的输出。 如您所见，该算法建议我们使用小雕像和喇叭，从而产生 14 磅的物品，价值 17 美元。

将 HorusLP 与 Gurobi 结合使用的好处之一是您可以“免费”获得大量信息。 在开发过程中通常希望查看的许多信息，例如每个变量的值、最终目标值和约束值，都会自动计算并以易于阅读的格式输出。

如果您阅读过上一篇关于 HorusLP 内核的文章，您会注意到这几乎是完全相同的 API。 为了保持 API 简单，HorusLP core 和 HorsLP-Gurobi 的接口是相同的，只是在超类实现中抽象出求解器之间的差异。

因此，我们将把 HorusLP 的介绍留给这个简单的例子； 可以在上一篇文章中找到演示 HorusLP 高级功能的更复杂示例。

Gurobi 功能

Gurobi 提供了许多用于解决复杂问题的高级功能。 大多数功能都可以通过 Model 对象访问。 为了与 Gurobi API 完全兼容，模型对象可以从问题类中轻松访问为model 。

例如，如果您想编写背包模型的 MPS 文件，在 Gurobi 中您可以编写类似m.write('knapsack.mps') 。 在使用 HorusLP-Gurobi 时，您可以简单地：

 # import the problem as usual from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE # define the constraint class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 # define the objectives as above class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn # define the variables used by the constraints and objectives class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') # define the problem as in the above example class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE # instantiate the problem. We don't need to call solve or print any reports. prob = KnapsackProblem() prob.model.write('knapsack.mps') # this is the only bit of new code!

您应该在工作目录中看到 MPS 文件。

您可以使用此界面访问高级 Gurobi 功能，例如计算 IIS、创建回调或提供变量提示。

为您服务的高级 Gurobi 功能

今天我们研究了基于 Gurobi Python API 构建的 HorusLP 库版本。 除了核心 HorusLP 的报告和调试功能外，您现在还可以通过与 Gurobi 的 Python API 集成无缝访问 Gurobi 的所有高级功能。

如果您是当前的 Gurobi 用户或对使用 Gurobi 优化感兴趣的人，希望您尝试一下 HorusLP！ 您可以在 GitHub 上找到示例代码、提出建议或为 HorusLP-Gurobi 做出贡献。