用Python进行线性编程 _线性编程

使用谷歌OR-工具的数学优化指南

文章插图
图片由作者提供，表情符号由 OpenMoji(CC BY-SA 4.0)
线性编程是一种优化具有多个变量和约束条件的任何问题的技术。这是一个简单但强大的工具，每个数据科学家都应该掌握。
想象一下，你是一个招募军队的战略家。你有

三种资源。食物、木材和黄金
三个单位：?剑客，弓箭手，和马兵。

骑士比弓箭手更强，而弓箭手又比剑客更强。下表提供了每个单位的成本和力量。

文章插图
图片由作者提供
现在我们有1200食物，800木材，600黄金。考虑到这些资源，我们应该如何最大化我们的军队的力量？
我们可以简单地找到能效/成本比最好的单元，尽可能多地取用它们，然后用另外两个单元重复这一过程。但这种 "猜测和检查 "的解决方案甚至可能不是最优的......
现在想象一下，我们有数以百万计的单位和资源：以前的贪婪策略很可能完全错过了最佳解决方案。使用机器学习算法（如遗传算法）来解决这个问题是可能的，但我们也不能保证解决方案是最优的。
幸运的是，有一种方法可以以最佳方式解决我们的问题：线性编程（或称线性优化），它属于 operations research(OR)的一部分。在这篇文章中，我们将用它来寻找剑客、弓箭手和骑兵的最佳数量，以建立具有最高力量的军队。
I. 求解器
在Python中，有不同的线性编程库，如多用途的SciPy、适合初学者的PuLP、详尽的Pyomo，以及其他许多库。
今天，我们将使用 google OR-Tools，它对用户非常友好，带有几个预包装的求解器，可以通过以下方式运行本教程中的代码 Google Colab notebook.
如果安装不成功，请重新启动内核并再试一次：它有时会失败。¯_(ツ)_/¯
!python -m pip install --upgrade --user -q ortools所有这些库都有一个隐藏的好处：它们作为接口，可以用不同的求解器使用同一个模型。解算器如 Gurobi, Cplex，或 SCIP有他们自己的API，但是他们所创建的模型是与特定的求解器相联系的。
OR-Tools允许我们使用一种抽象的（而且是相当pythonic的）方式来为我们的问题建模。然后我们可以选择一个或几个求解器来找到一个最佳解决方案。因此，我们建立的模型是高度可重复使用的

文章插图
图片由作者提供
OR-Tools带有自己的线性规划求解器，称为GLOP（谷歌线性优化包）。它是一个开源项目，由谷歌的运筹学团队创建，用C++编写。
其他求解器也是可用的，比如SCIP，这是一个优秀的非商业求解器，创建于2005年，并更新和维护至今。我们也可以使用流行的商业选项，如Gurobi和Cplex 。然而，我们需要将它们安装在OR-Tools之上，并获得适当的许可（这可能相当昂贵）。现在，让我们试试GLOP 。

# Import OR-Tools wrApper for linear programmingfrom ortools.linear_solver import pywraplp# Create a solver using the GLOP backendsolver = pywraplp.Solver('Maximize army power', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

II.变量
我们使用GLOP创建了一个OR-Tools求解器的实例。现在，如何使用线性编程？我们要定义的第一件事是我们要优化的变量。
在我们的例子中，我们有三个变量：军队中的?剑士、弓箭手和马兵的数量。OR-Tools接受三种类型的变量。

NumVar用于连续变量。
IntVar用于整数变量。
BoolVar用于布尔变量。

我们正在寻找单位的整数，所以让我们选择IntVar 。然后我们需要为这些变量指定下限和上限。我们希望至少有0个单位，但我们并没有真正的上限。所以我们可以说，我们的上界是无穷大（或任何我们永远不会达到的大数字）。它可以被写成。

文章插图

让我们把它翻译成代码。在OR-Tools中，Infinity被solver.infinity()所取代。除此以外，语法是非常直接的。

# Create the variables we want to optimizeswordsmen = solver.IntVar(0, solver.infinity(), 'swordsmen')bowmen = solver.IntVar(0, solver.infinity(), 'bowmen')horsemen = solver.IntVar(0, solver.infinity(), 'horsemen')

?? III.限制条件
我们定义了我们的变量，但约束条件也同样重要。