Python 混合整数线性规划

小开

最佳答案

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

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.

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

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

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

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.

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.

Also, have a look at this SO question.

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

I hope this helps!

UPDATES

More solvers and python interfaces that fell into my radar:

Update: MIPCL links appear to be broken. MIPCL, which appears to be 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 Optimization Tools, which include a multitude of functionalities, such as

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

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

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

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

小开

I have used Gekko Python Package to solve MILP problems. You can either solve your models locally or on their remote server. Below is an example after installing with 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 is 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.

小开

Soon there will be another option: Starting from version 1.9.0, SciPy will support MILP. See scipy.optimize.milp in the dev docs. The SciPy milp implementation is a wrapper of the HiGHS linear optimization software. It was added in this PR on February 16th, 2022.

Edit: SciPy 1.9.0 was released on July 29, 2022, with https://scipy.optimize.milp.