srcmini随着优化技术变得越来越复杂, 商业求解器已开始在行业中扮演越来越重要的角色。与开源求解器相比, 商业解决方案倾向于具有更多功能来解决复杂的优化模型, 例如高级预求解, 热启动和分布式求解。
市场上最受欢迎的商业求解器之一是Gurobi(Gurobi), 以共同创始人顾宗浩, 爱德华·罗斯伯格和罗伯特·比克斯比(Robert Bixby)的名字命名, 他们都是商业求解器领域的先驱。 Gurobi在最近的历史中为许多著名的优化项目提供了动力, 包括FCC的带宽分配项目和Pennsylvania State Prison的囚犯重新分配项目。
今天, 我们将研究如何为优化建模提供高级声明性界面的软件包HorusLP与Gurobi的API集成在一起, 从而在利用Gurobi最先进的功能的同时为用户带来直观的建模体验。
优化：快速刷新
对于那些不熟悉优化或运筹学的人, 优化是指一组数学技术, 这些数学技术可以在受约束系统约束的方程系统内找到变量的最优值。如果上面的句子听起来有些枯燥, 也许可以举一个例子来说明。
假设你有一个15磅承重的背包。你面前有几个项目, 每个项目都有特定的权重和货币价值：
- 相机：重量2磅, 价值$ 5
- 小雕像：重量4磅, 价值$ 7
- 苹果酒：重量7磅, 价值$ 2
- 喇叭：重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在用于判断商业和开放源代码求解程序的多个基准测试中始终表现出色。
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
荷鲁斯
HorusLP是一个优化建模库, 它建立在开发优化算法的经验上。当前可用的建模库缺少处理运筹学的商业应用通常遇到的复杂, 多方面的问题所需的工具。
尽管大多数优化库都提供了底层命令式界面, 但是随着优化模型变得越来越复杂, 需要更好的工具来管理复杂性。 HorusLP是一个提供高级工具来管理这些复杂性的库。 HorusLP还提供了功能强大的调试和报告工具, 可加快开发和迭代速度。
HorusLP的核心是一个面向对象的库, 它围绕优化模型提供了急需的体系结构。通过利用Python的面向对象语法, HorusLP库提供了一种结构, 可以在该结构周围优化模型。结果是一个解耦, 模块化且易于阅读的代码库。
如果你想对带有代码示例的核心HorusLP库进行更详细的介绍, 可以在这里找到教程。
HorusLP-Gurobi整合
虽然HorusLP的核心API为构建优化模型提供了方便的高级API, 但它是基于PuLP构建的, 尽管PuLP能够将Gurobi用作求解器, 但无法使用Gurobi的某些更高级的功能。
HorusLP-Gurobi是使用Gurobi的Python API构建的HorusLP API的版本。这使用户可以直接访问Gurobi的高级功能, 同时保持HorusLP API的一致性。
指导HorusLP-Gurobi开发的主要哲学之一是与HorusLP核心API保持一致。通过保持HorusLP的简约结构一致, 开源求解器的用户可以通过安装Gurobi API并切换import语句轻松地过渡到使用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
然后我们实例化问题并调用Solve函数。这就是魔术发生的地方。
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核心和HorsLP-Gurobi的接口是相同的, 在超类实现中抽象出了求解器之间的差异。
因此, 我们将把HorusLP的介绍留给这个简单的例子。在上一篇文章中可以找到更复杂的示例, 它们演示了HorusLP的高级功能。
Gurobi特色
Gurobi提供了许多用于解决复杂问题的高级功能。可通过Model对象访问大多数功能。为了与Gurobi API完全兼容, 可以从问题类作为模型轻松访问模型对象。
例如, 如果你想编写背包模型的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做出贡献。
评论前必须登录！
注册