Python混合整数线性规划

Python Mixed Integer Linear Programming

提问by asun

Are there any Mixed Integer Linear Programming(MILP) solver for Python?

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

Can GLPK python solve MILP problem? I read that it can solve Mixed integer problem.
I am very new to linear programming problem. So i am rather confused and cant really differentiate if Mixed Integer Programming is different from Mixed Integer Linear programming(MILP).

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

采纳答案by Ioannis

Pulpis a python modeling interface that hooks up to solvers like CBC(open source), CPLEX(commercial), Gurobi(commercial), XPRESS-MP(commercial) and YALMIP(open source).

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

You can also use Pyomoto model the optimization problem and then call an external solver, namely CPLEX, Gurobi GLPK and the AMPL solver library.

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

You can also call GLPK from GLPK/Python, PyGLPKor PyMathProg.

您还可以从GLPK/Python、PyGLPK或PyMathProg调用 GLPK 。

Yet another modelling language is CMPL, which has a python interface for MIP solvers (for linear programs only).

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

All the above solvers solve Mixed Integer LinearPrograms, while some of them (CPLEX, GUROBI and XRESS-MP for sure) can solve Mixed Integer QuadraticProgramsand Quadratically constrained quadratic programs(and also conic programs but this probably goes beyond the scope of this question).

以上所有求解器都解决了混合整数线性程序，而其中一些（肯定是 CPLEX、GUROBI 和 XRESS-MP）可以解决混合整数二次程序和二次约束二次程序（还有圆锥程序，但这可能超出了本文的范围）题）。

MIP refers to Mixed integer programs, but it is commonly used to refer to linear programs only. To make the terminology more precise, one should always refer to MILP or MINLP (Mixed integer non-linear programming).

MIP 指的是混合整数规划，但通常仅用于指代线性规划。为了使术语更精确，应始终参考 MILP 或 MINLP（混合整数非线性规划）。

Note that CPLEX and GUROBI have their own python APIs as well, but they (and also) XPRESS-MP are commercial products, but free for academic research. CyLPis similar to Pulp above but interfaces with the COIN-OR solvers CBC and CGL and CLP.

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

Note that there is a big difference in the performance of commercial and free solvers: the latter are falling behind the former by a large margin. SCIPis perhaps the best non-commercial solver(see below for an update). Its python interface, PySCIPOpt, is here.

请注意，商业和免费求解器的性能存在很大差异：后者大大落后于前者。SCIP是也许是最好的非商业求解器（请参阅下面的更新）。它的 Python 接口 PySCIPOpt在这里。

Also, have a look at this SO question.

另外，看看这个 SO question。

Finally, if you are interested at a simple constraint solver (not optimization) then have a look at python-constraint.

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

I hope this helps!

我希望这有帮助！

UPDATES

更新

More solvers and python interfaces that fell into my radar:

更多的求解器和 python 接口落入了我的视线：

MIPCL, which appears to be one of the fastestthe fastest non-commercial MIP solver, has a python interfacethat has quite good documentation. Note, however, that the Python API does not include the advanced functionality that comes together with the native MIPCLShell. I particularly like the MIPCL-PY manual, which demonstrates an array of models used in Operations Management, on top of some small-scale implementations. It is a very interesting introductory manual in its own right, regardless of which solver/API one may want to make use of.

MIPCL似乎是最快、最快的非商业 MIP 求解器之一，它有一个Python 接口，里面有很好的文档。但是请注意，Python API 不包括与本机MIPCLShell一起提供的高级功能。我特别喜欢MIPCL-PY 手册，它在一些小规模实现的基础上展示了运营管理中使用的一系列模型。它本身就是一本非常有趣的介绍手册，无论人们可能想要使用哪种求解器/API。

Google Optimization Tools, which include a multitude of functionalities, such as

Google 优化工具，其中包括多种功能，例如

• A constraint programming solver and a linear programming (not MIP) solver
• An interface for MIP solvers (supports CBC, CLP, GLOP, GLPK, Gurobi, CPLEX, and SCIP)
• Specialized algorithms for graphs, for the Travelling Salesman Problem, the Vehicle Routing problem and for Bin packing & Knapsack problems

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

It has extensive documentation of several traditional OR problems and simple implementations. I could not find a complete Python API documentation, although there exist some examples here. It is somewhat unclear to me how other solvers hook up on the interface and whether methods of these solvers are available.

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

CVXOPT, an open-source package for convex optimization, which interfaces to GLPK (open source) and MOSEK(commercial). It is versatile, as it can tackle many problem classes (notably linear, second-order, semidefinite, convex nonlinear). The only disadvantage is that it modeling complex problems may be cumbersome, as the user needs to pass the data in a "Matlab-y" fashion (i.e., to specify the matrix, rhs vectors, etc). However, it can be called from the modeling interfaces PICOSand...

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

CVXPY, a python-embedded optimization language for convex optimization problems, which contains CVXOPTas a default solver, but it can hook up to the usual MIP solvers.

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

Thanks to RedPandafor pointing out that CVXOPT/CVXPYsupport MIP solvers as well.

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

For a very comprehensive article on optimization modeling capabilities of packages and object-oriented languages (not restricted to Python), check this article.

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

回答by Muhammad Ali

I have used Gekko Python Package to solve MILP problems. You can either solve your models locally or on their remote server.

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

GEKKOis a Python package for machine learning and optimization of mixed-integer and differential algebraic equations. It is coupled with large-scale solvers for linear, quadratic, nonlinear, and mixed integer programming (LP, QP, NLP, MILP, MINLP). Modes of operation include parameter regression, data reconciliation, real-time optimization, dynamic simulation, and nonlinear predictive control. GEKKO is an object-oriented Python library to facilitate local execution of APMonitor.

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