Python Mixed Integer Linear Programming

by

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.

More Related Contents:

  1. pandas, melt, unmelt preserve index
  2. Whats wrong with my JSON Object [closed]
  3. How to use a decimal range() step value?
  4. Your CPU supports instructions that this TensorFlow binary was not compiled to use: AVX AVX2
  5. How to check if the string is empty?
  6. How to include third party Python libraries in Google App Engine?
  7. Python: Maximum recursion depth exceeded
  8. ‘module’ object has no attribute ‘loads’ while parsing JSON using python
  9. setting an environment variable in virtualenv
  10. How do I create animated sprites using Sprite Sheets in Pygame?
  11. Why don’t methods have reference equality?
  12. Python datetime to string without microsecond component
  13. Reading dynamically generated web pages using python
  14. How to print a percentage value in python?
  15. AttributeError: ‘datetime’ module has no attribute ‘strptime’
  16. How to use a Keras RNN model to forecast for future dates or events?
  17. Exclude type in Python typing annotation
  18. Error “Read-only file system” in AWS Lambda when downloading a file from S3
  19. “public” or “private” attribute in Python ? What is the best way?
  20. How to install SIP & PyQT on windows 7
  21. Simultaneous assignment semantics in Python
  22. Does R have function startswith or endswith like python? [closed]
  23. Pandas: Reading Excel with merged cells
  24. How to Print “Pretty” String Output in Python
  25. how to share a variable across modules for all tests in py.test
  26. How to tell if one regular expression matches a subset of another regular expression?
  27. How to convert list of strings to their correct Python types?
  28. Can’t concat bytes to str
  29. Bundling Data files with PyInstaller 2.1 and MEIPASS error –onefile
  30. The ‘pip==7.1.0’ distribution was not found and is required by the application

Leave a Comment