Python混合整数线性规划

Question

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

GLPK python可以解决MILP问题吗？我读到它可以解决混合整数问题.
我对线性编程问题很新.所以我很困惑,如果混合整数规划与混合整数线性规划(MILP)不同,则无法区分.

Answer 1

Pulp是一个python建模界面,可以连接到 CBC(开源), CPLEX(商业), Gurobi(商业), XPRESS-MP(商业)和 YALMIP(开源)等解决方案.

您还可以使用Pyomo对优化问题进行建模,然后调用外部求解器,即CPLEX,Gurobim GLPK和AMPL求解器库.

您也可以从GLPK/Python,PyGLPK或PyMathProg调用GLPK .

另一种建模语言是CMPL,它具有用于MIP求解器的python接口(仅用于线性程序).

所有上述解算器都解决了混合整数线性程序,而其中一些解决方案(CPLEX,GUROBI和XRESS-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似乎是最快的非商业MIP解算器之一,它有一个python接口,具有相当好的文档.但请注意,Python API不包含与本机MIPCLShell一起提供的高级功能.我特别喜欢MIPCL-PY手册,它在一些小规模实现之上演示了运营管理中使用的一系列模型.无论使用哪种求解器/ API,它本身都是一本非常有趣的入门手册.

Google优化工具,包含众多功能,例如

• 约束编程求解器和线性编程(非MIP)求解器
• MIP求解器的接口(支持CBC,CLP,GLOP,GLPK,Gurobi,CPLEX和SCIP)
• 用于图表的专用算法,用于旅行商问题,车辆路径问题以及Bin包装和背包问题

它包含了几个传统OR问题和简单实现的大量文档.我找不到一个完整的Python API文档,尽管存在一些例子在这里.我有点不清楚其他求解器如何连接接口以及这些求解器的方法是否可用.

CVXOPT,一个用于凸优化的开源软件包,可与GLPK(开源)和MOSEK (商业)接口.它是多功能的,因为它可以解决许多问题类别(特别是线性,二阶,半定,凸非线性).唯一的缺点是,对复杂问题进行建模可能很麻烦,因为用户需要以"Matlab-y"方式传递数据(即,指定矩阵,rhs向量等).但是,可以从建模接口PICOS调用它...

CVXPY,一种用于凸优化问题的python嵌入式优化语言,它包含CVXOPT作为默认求解器,但它可以连接到通常的MIP求解器.

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

有关包和面向对象语言(不限于Python)的优化建模功能的非常全面的文章,请查看本文.

Answer 2

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

编辑： SciPy 1.9.0于 2022 年 7 月 29 日发布，带有scipy.optimize.milp。

Answer 3

我使用 Gekko Python Package 来解决 MILP 问题。您可以在本地或远程服务器上求解模型。

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