Python Mixed Integer Linear Programming

Question

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

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

Moxa

i am not too sure why the down vote, but i have actually searched for hours, and was really not sure whether MILP is same as MIP. – Moxa

Answer 1

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.

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.

Terrence

hey, thanks for the reply. I have searched many of the stuffed you posted. Even installed two of them(PuLP and GLPK) before posting this. Because of the naming, i was rather confused between MILP and MIP. Anyway, thanks for the clarification. Appreciated. – Moxa

By the way, there is vastly imporved Python interface for SCIP that can be found here: github.com/SCIP-Interfaces/PySCIPOpt – Tread

@Tread Link updated. Thanks for working on this! – Terrence

cvxopt and cvxpy also support mixed integer programming. Here's an article benchmarking cvxopt as much faster than pulp: scaron.info/blog/linear-programming-in-python-with-cvxopt.html – Humph

I don't think Gurobi is open source as stated in the first sentence of the answer. – Postpone

@loannis "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". I've also noticed. Do you know why this is? For almost any other computing task (array operations, machine learning, etc), I've found the free options to be competitive. Why not here? – Postpone

@loannis If only the last one is open source, maybe also get rid of "the open source". Or is CBC also open source? – Postpone

@OliverAngelil The complexity of a MIP solver is not comparable with that of regular numerical analysis subroutines, such as array operations, solving systems of equations etc. This is mainly for two reasons. First, there is a lot of historical knowledge embedded in the solvers, spanning decades of rigorous research and implementation-specific details. Second, solving MIP problems is an active area of research, with scholars pushing the boundaries of what can be solved year on year. Commercial solvers implement the new advances regularly, updating their versions about once per year. – Terrence

What's the basis for the claim that MIPCL is the fastest? These benchmarks do seem to confirm your claim: plato.asu.edu/talks/ismp2018.pdf . Unfortunately the list doesn't distinguish between commercial/non-commercial. (As far as I can tell, GLPK, CBC, lp_solve, MIPCL are fully open-source, SCIP is non-commercial.) – Scharf

Has MIPCL died? The links don’t work any more. – Deepdyed

@Anush Indeed, MIPCL links appear to be broken. There is a github repo (see this, but installation seems to be troublesome here SO post). At the time, it used to be a good choice, but I would opt for another alternative today. – Terrence

That's a shame. cvxpy.org/en/latest/tutorial/advanced/… is also broken (you have it as a link) So is cvxpy.org/en/latest/tutorial/intro/index.html – Deepdyed

Thanks for noticing @Anush; I have updated the corresponding links. – Terrence

@loannis Thanks for this excellent answer, I learned a lot. I have a follow-up questions about MILP solvers, Is there an open source MILP solver that can output top N best solutions rather than the global best? – Aplanospore

@Aplanospore Glad you found the answer helpful. Some solvers (CPLEX, Gurobi) allow you to collect the solutions found through the search (e.g., check here and here). For certain models, we may be able to retrieve other optimal solutions (e.g., if symmetries exist), or iteratively rule out solutions. Also, check Paul Rubin's blog (a treasure trove for MIP optimization) here. – Terrence

Answer 2

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 scipy.optimize.milp.

Fehr

Answer 3

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.

Alecto

Here are code examples of MILP solved with gekko using dense and sparse matrices: apmonitor.com/wiki/index.php/Main/IntegerProgramming – Skite