Python中的整数编程

Python 6月前 6

整数编程问题是指通过规定问题中涉及的部分或全部变量为整数而构建的问题，以确保数学上的优化或可行性。

假设问题中的一些决策变量被发现不是离散的。在这种情况下，它们被归类为混合整数问题，更常见的是MIP/MILP （混合整数线性编程）。

所以在这篇Python文章中，我们将探索各种方法和库，我们可以用Python来解决这类问题。

Python中的混合整数编程问题

混合整数编程 (MIP) 问题是一个问题，其中一些决策变量被确保为严格的整数值，以获得最优解。

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

MIP 中的一个基本情况是决策变量被认为是二进制的；换句话说，它只能被表示为0 或1 。

这些通常被称为二进制整数值。这些决策变量通常用于建立True/False 或Yes/No 决策模型，基于仔细计算。

现在有几个求解器被设计来处理这类问题。

其中包括最先进的Gurobi 和Python-MIP ，是最常见的和最受欢迎的混合整数线性规划求解器。

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

它提供了高端和现代的功能，在下面有详细的描述和解释。

用于`MIP/MILP` 的 Python 工具：`Python-MIP`

在Python中，我们有一个庞大的库，称为MIP ，基本上是一个基于Python的工具集合，用于建模和解决混合整数线性编程问题。

MIP 的语法受Pulp 的启发很大，它为用户提供了先进和有效的功能，如lazy constraints 、MIPstart 、solution pools 和cut generation 。

其更多的突出特点包括：

高级建模

大多数程序员都使用高级编程语言发展了他们的建模技能，因为它很容易。然而，我们可以用Python快速编写我们的MIP models 。

操作符重载功能使得在Python中编写线性表达式的整个过程更加顺畅。
功能打包

有了像cut generators 和lazy constraints 这样的功能，程序员可以使用许多约束条件来处理坚实的公式。

在branch and cut 搜索过程中，它只生成所需的不等式。然后，为了补充，你可以查询到solution pool ，以提取或浏览在搜索过程中发现的一流的解决方案。

此外，MIPstart ，使程序员最初利用一个与问题有关的启发式方法，为MIP 搜索创建可行的解决方案。
快速和高效

Python中的MIP 包使已经安装的求解器的本地动态可加载库直接call ，使用CFFI module 。

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

它运行25 的速度比它快，因为它的性能只基于CPython 。
多重化解

MIP 的构造是为了与解算器和的彻底整合。COIN-OR Branch-&-Cut Gurobi C-based libraries

有了MIP ，你不必担心编写不同求解器之间的通信手段，因为这在Python-MIP 库中已经处理了。

你只需要写一个独立于求解器的代码。
配备了最新的Python版本

如上所述，MIP 与Python 3.6及以上版本兼容，所以我们不必担心冗余会拖累你。