Python混合整数线性编程 [英] Python Mixed Integer Linear Programming

问题描述

是否有适用于Python的混合整数线性编程(MILP)求解器?

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

GLPK python可以解决MILP问题吗?我读到它可以解决混合整数问题.
我对线性编程问题很陌生.因此，如果混合整数编程与混合整数线性编程(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).

推荐答案

纸浆 是一个python建模界面，可连接到 CBC (开源)， CPLEX (商业)， 古罗比 (商业)，

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

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

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

您还可以从 GLPK/Python 调用GLPK ， PyGLPK 或

You can also call GLPK from GLPK/Python, PyGLPK or PyMathProg.

另一种建模语言是 CMPL ，该语言具有用于MIP求解器(仅适用于线性程序).

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

以上所有求解器均求解混合整数线性程序，而其中一些(肯定是CPLEX，GUROBI和XRESS-MP)可以解决混合整数二次方程序和二次约束二次方程序(以及圆锥形程序，但这可能超出了此问题的范围).

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

MIP指混合整数程序，但通常仅用于指线性程序.为了使术语更精确，应该始终参考MILP或MINLP(混合整数非线性编程).

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).

请注意，CPLEX和GUROBI也具有自己的python API，但它们(以及)XPRESS-MP是商业产品，但对于学术研究是免费的. CyLP 与上面的Pulp类似，但与COIN-OR求解器接口CBC，CGL和CLP.

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. CyLP is similar to Pulp above but interfaces with the COIN-OR solvers CBC and CGL and CLP.

请注意，商业解决方案和免费解决方案的性能有很大差异:后者落后于后者前者大有作为. SCIP 是 最好的非商业解决方案 (有关更新，请参见下文).它的python接口PySCIPOpt是 此处 .

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. SCIP is perhaps the best non-commercial solver (see below for an update). Its python interface, PySCIPOpt, is here.

此外，请查看这个SO问题.

最后，如果您对简单的约束求解器(而非优化)感兴趣，请查看 python -constraint .

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

我希望这会有所帮助！

更多的求解器和python接口掉入了我的雷达:

More solvers and python interfaces that fell into my radar:

MIPCL ，它似乎是最快的之一最快的非商业MIP求解器，具有 python界面具有相当好的文档.但是请注意，Python API不包括与本机 MIPCLShell一起提供的高级功能. .我特别喜欢 MIPCL-PY手册，该手册演示了一个数组一些小型实现基础上的Operations Management中使用的模型的集合.无论您想使用哪种求解器/API，它本身都是一本非常有趣的入门手册.

MIPCL, which appears to be one of the fastest the fastest non-commercial MIP solver, has a python interface that 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.

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

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

• 约束规划求解器和线性规划(非MIP )求解器
• 用于MIP求解器的界面(支持CBC，CLP，GLOP，GLPK，Gurobi，CPLEX和SCIP)
• 用于图形，旅行推销员问题，车辆路线问题以及箱装箱和卸货的专用算法.背包问题

• 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

它具有有关多个传统OR问题和简单实现的大量文档.我找不到完整的Python API文档，尽管在此处中有一些示例.对我来说，还不清楚其他求解器如何在接口上连接，以及这些求解器的方法是否可用.

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.

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

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 PICOS and...

CVXPY ，这是python嵌入式的凸出优化语言优化问题，其中包含CVXOPT作为默认求解器，但它可以关联至常用的MIP求解器.

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

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

Thanks to RedPanda for pointing out that CVXOPT/CVXPY support MIP solvers as well.

要获得有关软件包和面向对象语言(不限于Python)的优化建模功能的非常全面的文章，请查看这篇文章.

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

这篇关于Python混合整数线性编程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！