实例详解:用Python解决整数规划问题!

我们将使用整数规划来做出最佳决策

整数规划（IP）问题是所有变量都被限制为整数的优化问题（指规划中的变量（全部或部分）限制为整数，若在线性模型中，变量限制为整数，则称为整数线性规划）。IP问题是有关于如何最好地分配资源的有用数学模型。

假设你正在组织针对政治候选人的营销活动，并且你正在决定向哪些组成部分发送营销材料。你可以向每个组织发送一张吸引人的传单，一份详细的解释你的日程表的小册子，或一张保险杠贴纸（或三者的组合）。如果你有办法根据收到的营销材料来衡量某人投票给候选人的可能性，你如何决定发送哪些材料，同时不超过你的供应量？

传统的优化算法假定变量可以采用浮点值，但在我们的例子中，向某人发送一半保险杠贴纸或四分之三小册是不合理的。我们将使用一个名为cvxpy的特殊python包来解决我们的问题，这样解决方案才有意义。

这里将向你展示如何使用cvxpy解决政治候选人问题，首先会从一个简单的问题开始，称为背包问题，然后展示cvxpy语法的工作原理。

背包问题

让我们假装你正在进行徒步旅行，并且正在计划你可以携带的物品。你想把所有的东西都拿走，但是你的背包只能携带P磅。假设你可以取一个物体，目标是最大限度地提高实用性，而不会超出重量限制。

一个cvxpy问题有三个部分：

1.创建变量：我们将用1和0的向量在数学上表示我们的选择。 1意味着我们选择了这个对象，而0意味着我们将它留在家中。我们用cvxpy.Bool对象构造一个只能取1和0的变量。

2.指定约束条件：我们只需确保我们的对象总和不超过重量限制P。我们可以用选择向量和权向量的点积来计算我们对象的总重量。cvxpy会重载*运算符以执行矩阵乘法。

3.制定目标函数：我们希望最大化选择的效用。任何给定选择的效用都是选择向量和效用向量的点积。

完整的背包问题的cvxpy代码

一旦我们有成本函数和约束，我们将它们传递给cvxpy 问题对象。在这种情况下，cvxpy要试图通过cvxpy.Maximize最大化实用程序。为了解决这个问题，我们只需要运行问题对象的求解方法。之后，我们可以通过查看它的值属性来检查我们选择向量的最优值。

我们选择了前四项和第六项。这是有道理的，因为这些具有很高的效用与重量的比例，但又不会过重。

营销问题

现在我们已经介绍了基本的cvxpy语法，我们可以为我们的政治候选人解决营销优化问题。假设我们有一个模型，它接受一个组成部分的属性，并预测他们将为我们的候选人投票给我们发送的每个营销材料组合的概率。我在这里使用假数据，让我们假装模型输出以下概率：

每个组织有八个总概率，因为我们可以向个人发送八种材料的总组合。以下是每个1 x 8向量表示的条目：

[1份传单、1本小册子、1份保险杠贴纸、传单和小册子、传单和保险杠贴纸、小册子和保险杠贴纸、全部三种]。

例如，如果我们的候选人收到传单或小册子，那么第一个成员对我们的候选人的投票概率为0.0001，但是如果我们给他发了一个保险杠贴纸，我们的候选人有0.3的概率投票。

在我们开始使用cvxpy代码之前，我们将通过采用negative log将这些概率转化为成本。这使得数学工作变得更好，并且它有一个很好的解释：如果概率接近1，negative log将接近于0，这意味着将该材料的特定组合发送到该组成部分几乎没有成本，因为我们肯定会导致他们投票给我们的候选人。反之亦然，如果概率接近于0。

最后，假设我们不能发送超过150张传单，80张小册子和25张保险杠贴纸。

现在我们已经完成了所有的设置，发现一些有趣的部分：

1.创建变量：我们将再次使用cvxpy.Bool对象，因为我们只能在这里创建二进制选项。我们将指定它必须与我们的概率矩阵形状相同：

2.指定约束条件：我们的选择变量只会告诉我们为每个组成部分选择了8个选项中的哪一个，但它不会告诉我们已决定发送给他们的总共多少材料。我们需要一种方法将我们的1 x 8选择向量转换为1 x 3向量。我们可以通过乘以选择向量乘以下面的矩阵来实现：

如果这部分有点令人困惑，那么请看下面的例子：

我们的决策向量的第四个条目表示向组件发送传单和小册子，乘以变压器告诉我们！所以我们会让cvxpy乘以变压器的选择矩阵不能超过我们的供应：

这里用cvxpy.sum_entries对行进行总结，以汇总我们发送到所有组成部分的材料总数。

我们还需要确保每个组成部分的选择都是正确的，否则求解者可以通过不发送任何东西来实现零成本。

3.制定目标函数：我们的任务总成本将是我们为每个成员承担的成本的总和。我们将使用cvxpy.mul_elemwise函数将我们的选择矩阵与成本矩阵相乘，这将选择每个成分的成本，并且cvxpy.sum_elemwise函数将通过累计单个成本来计算总成本。

最后一步是创建cvxpy.Problem并解决它。

就是这样！以下是我们最终作业的截图。我们决定不向第一个组织发送任何材料。这是有道理的，因为他们为我们的候选人投票的可能性是0.3，不管我们给他们发一张保险杠贴纸还是什么都不发。

它也证明，最优的分配方案会耗尽我们的小册子和保险杠贴纸的供应，但其实只使用了150传单中的83张。我们应该告诉我们的候选人她的传单并没有她想象的那么有说服力。

以下是所有打包在一起的代码：

结束语

希望这篇整数规划问题以及如何用Python解决它们能够对你有作用。我们已经覆盖了大约80％的cvxpy知识，你需要去解决你自己的优化问题。当然，可以阅读官方文件，从而了解剩下的20％。 CVXPY不仅可以解决IP问题，还可以查看他们的教程页面，查看cvxpy可以解决的其他问题。

要安装cvxpy，请按照其网站上的指示进行操作。我还会安装cvxopt，以确保所有使用cvxpy打包的求解器都可以在你的机器上运行。

我们已经指定cvxpy应该在解决方法中使用GLPK_MI求解器。这是专为解决IP问题而设计的解决方案。在你解决你自己的问题之前，请参考这个表格，看看哪个预包装的cvpxy求解器最适合你。