Python混合整数线性规划

Question

是否有适用于Python的混合整数线性规划（MILP）求解器？

GLPK Python是否能够解决MILP问题？我读到它可以解决混合整数问题。
我对线性规划问题非常陌生，所以我很困惑，无法真正区分混合整数编程与混合整数线性编程（MILP）是否不同。

- asun

---

我不太确定为什么会有人给我负评，但我实际上已经搜寻了数小时，而且确实不确定 MILP 是否与 MIP 相同。 - asun

Answer 1

Pulp是一个Python建模接口，可连接到求解器如CBC（开源），CPLEX（商业），Gurobi（商业），XPRESS-MP（商业）和YALMIP（开源）。

您还可以使用Pyomo来建立优化问题模型，然后调用外部求解器，即CPLEX、Gurobi GLPK和AMPL求解器库。

你可以通过GLPK/Python、PyGLPK或PyMathProg调用GLPK。

另一种建模语言是CMPL，它有一个用于MIP求解器的Python接口（仅适用于线性规划）。

所有上述求解器都可以解决混合整数线性规划问题，但其中一些求解器（如CPLEX、GUROBI和XPRESS-MP）可以解决混合整数二次规划问题和二次约束二次规划问题（以及锥形规划问题，但这可能超出了本问题的范围）。

MIP指混合整数规划问题，但通常用于仅指线性规划问题。为了使术语更加精确，应始终引用MILP或MINLP（混合整数非线性规划问题）。

请注意，CPLEX和GUROBI也有自己的Python API，而它们（以及XPRESS-MP）是商业产品，但可以免费用于学术研究。CyLP与上面的Pulp类似，但它与COIN-OR求解器CBC、CGL和CLP进行接口。

请注意商业求解器和免费求解器的性能差异很大：后者在很大程度上落后于前者。 SCIP是也许是最好的非商业求解器（有关更新，请参见下文）。其Python接口PySCIPOpt在此处。

另外，请查看这个SO问题。

最后，如果您对简单的约束求解器（而不是优化）感兴趣，请查看python-constraint。

更新

我发现了更多的求解器和Python接口：

更新：MIPCL链接似乎已经失效。 MIPCL，看起来是最快的非商业MIP求解器，有一个Python接口，并且有相当好的文档。但是请注意，Python API不包括与本地MIPCLShell一起提供的高级功能。我特别喜欢MIPCL-PY手册，其中演示了在运营管理中使用的一系列模型，以及一些小规模实现。这是一个非常有趣的入门手册，无论想要使用哪个求解器/API都可以参考。

Google Optimization Tools是一款包含多种功能的工具，例如：

• 限制编程求解器和线性规划（非MIP）求解器
• MIP求解器接口（支持CBC、CLP、GLOP、GLPK、Gurobi、CPLEX和SCIP）
• 专用于图形、旅行商问题、车辆路径问题以及装箱与背包问题的算法

它有关于几个传统OR问题和简单实现的广泛文档。我找不到完整的Python API文档，虽然这里有一些示例here。我不太清楚其他求解器如何连接到接口上，以及这些求解器的方法是否可用。

CVXOPT，一个用于凸优化的开源软件包，它与GLPK（开源）和MOSEK接口。它非常灵活，可以解决许多问题类别（尤其是线性、二阶、半定、凸非线性）。唯一的缺点是建模复杂问题可能很繁琐，因为用户需要以“Matlab-y”方式传递数据（即指定矩阵、rhs向量等）。但是，它可以从建模接口PICOS调用...

CVXPY，一种嵌入Python语言的凸优化语言，它默认包含CVXOPT作为求解器，但它也可以连接到通常的MIP求解器中。

感谢RedPanda指出CVXOPT/CVXPY也支持MIP求解器。

关于软件包和面向对象语言（不仅限于Python）的优化建模能力的非常全面的文章，请查看this article。

- Ioannis

---

顺便提一下，SCIP有一个大大改进的Python接口，可以在这里找到：https://github.com/SCIP-Interfaces/PySCIPOpt - mattmilten

cvxopt和cvxpy也支持混合整数规划。这里有一篇文章对cvxopt进行了基准测试，结果比pulp快得多：https://scaron.info/blog/linear-programming-in-python-with-cvxopt.html - RedPanda

我认为Gurobi不是开源的，正如答案的第一句话所述。 - Oliver Angelil

MIP求解器的复杂性与常规数值分析子程序（例如数组操作、解方程组等）不可比较。这主要有两个原因。首先，求解器中嵌入了大量历史知识，涵盖了几十年的严格研究和实现细节。其次，解决MIP问题是一个活跃的研究领域，学者们每年都在推动能够解决的问题的边界。商业求解器定期实现新的进展，每年更新一次版本。 - Ioannis

MIPCL死了吗？链接不再有效。 - Simd

Answer 2

很快就会有另一种选择：从版本1.9.0开始，SciPy将支持MILP。请参阅开发文档中的scipy.optimize.milp。SciPy的milp实现是HiGHS线性优化软件的包装器。它是在2022年2月16日的这个PR上添加的。

编辑：SciPy 1.9.0已于2022年7月29日发布，其中包含scipy.optimize.milp。

- Ewout ter Hoeven

Answer 3

我已经使用Gekko Python包来解决MILP问题。您可以在本地解决模型，也可以在其远程服务器上进行求解。安装后，您可以通过pip install gekko来使用它。下面是一个例子：

from gekko import GEKKO
m = GEKKO()
x,y = m.Array(m.Var,2,integer=True,lb=0) 
m.Maximize(y)
m.Equations([-x+y<=1,
             3*x+2*y<=12,
             2*x+3*y<=12])
m.options.SOLVER = 1
m.solve()
print('Objective: ', -m.options.OBJFCNVAL)
print('x: ', x.value[0])
print('y: ', y.value[0])

GEKKO 是一款用于机器学习和混合整数微分代数方程优化的Python软件包。它与大规模求解器（线性、二次、非线性和混合整数规划LP、QP、NLP、MILP、MINLP）结合使用。其操作模式包括参数回归、数据协调、实时优化、动态仿真和非线性预测控制。GEKKO是一个面向对象的Python库，以促进APMonitor的本地执行。

- Muhammad Ali

---

以下是使用密集矩阵和稀疏矩阵解决 MILP 的 gekko 代码示例：https://apmonitor.com/wiki/index.php/Main/IntegerProgramming - John Hedengren