迹忆客 专注技术分享

整数规划问题是通过提供问题中涉及的部分或全部变量为整数来确保数学优化或可行性的问题。

假设发现问题中的某些决策变量不是离散的。 在那种情况下，它们被归类为混合整数问题，通常称为 MIP/MILP（混合整数线性规划）。

因此，在这篇 Python 文章中，我们将探讨可用于在 Python 中解决此类问题的各种方法和库。

Python 中的混合整数规划问题

混合整数规划 (MIP) 问题是其中一些决策变量被确保为最优解的严格整数值的问题。

使用这些整数变量拓宽了有用的优化问题的视野和分数，程序员可以使用这些问题最有效、最准确地定义和解决。

MIP 中的一个基本场景是将决策变量视为二进制； 换句话说，它只能表示为 0 或 1。

这些通常称为二进制整数值。 这些决策变量通常用于根据仔细计算对真/假或是/否决策进行建模。

现在有几个求解器可以用来处理这类问题。

其中包括最先进的 Gurobi 和 Python-MIP，它们是最广为人知和最受欢迎的混合整数线性规划求解器。

另一个高度可配置的 MIP 求解器是 CBC 或 COIN-OR Branch-&-Cut 求解器。 最后，Python-MIP 使得为任何自定义应用程序开发高性能、基于 MIP 的求解器变得容易。

它提供了高端和现代的功能，下面将对其进行详细描述和解释。

MIP/MILP 的 Python 工具：Python-MIP

在 Python 中，我们有一个名为 MIP 的庞大库，它本质上是一组基于 Python 的工具，用于建模和解决混合整数线性规划问题。

MIP 的语法深受 Pulp 的启发，为用户提供了高级和高效的功能，如惰性约束、MIPstart、解决方案池和剪切生成。

它的更多突出特点包括：

• 高级建模

  大多数程序员已经发展了使用高级编程语言进行建模的技能，因为它很容易。 但是，我们可以用 Python 快速编写 MIP 模型。

  运算符重载特性使得在 Python 中编写线性表达式的整个过程更加顺畅。

• 功能丰富

  借助切割生成器和惰性约束等功能，程序员可以使用许多约束来处理实体公式。

  它仅生成分支切割搜索期间所需的不等式。 然后，要添加，您可以查询到解决方案池以提取或浏览在搜索过程中找到的一流解决方案。

  此外，MIPstart 使程序员能够最初利用问题相关的启发式方法为 MIP 搜索创建可行的解决方案。

• 快速高效

  Python 中的 MIP 包使用 CFFI 模块直接调用已安装求解器的本机动态可加载库。

  这些模型被求解器有效地存储和提高效率。 同时，MIP 处理与您的代码的通信。 虽然官方 Gurobi Python 接口也提供了处理 MILP 的功能，但 Python 中的 MIP 库与 Pypy 兼容。

  它的运行速度比它快 25 倍，因为它的性能仅基于 CPython。

• 多解

  Python 中的 MIP 被构建为与 COIN-OR Branch-&-Cut 求解器和 Gurobi 的基于 C 的库完全集成。

  使用 MIP，您不必担心编写不同求解器之间的通信方式，因为它在 Python-MIP 库中进行了处理。

  您只需编写一个独立于求解器的代码。

• 配备最新的 Python 版本

  如上所述，MIP 与 Python 3.6 及以上版本兼容，因此我们不必担心冗余会拖慢您的速度。

现在您知道什么是混合整数规划以及可用于指导您解决任何可能需要以最有效和最有用的优化方式解决的整数规划问题的不同求解器。

您还可以浏览所有提及的求解器的官方文档，以找到针对您的特定问题的解决方案。