Linear Programming in Python with CVXOPT

Often we want to maximize/minimize a function w.r.t some exterior constraints. This can be easily done in Python using the CVXOPT package.

Tutorial examples for the linear and quadratic cases are available: linear, quadratic.

One of the main problems with this package is the installation - doing it via the standard method of pip or homebrew is possible but there is a caveat: for linear programming you want to use the 3rd party solver glpk. This has been optimised for linear functions and consequently is much (~100 times) faster than the standard, more general CVXOPT solver.

The best way to do this is to install glpk with homebrew:

brew install glpk


and then manually download the CVXOPT package. Unzip the tarball, and then in setup.py change the variables as:

BUILD_GLPK = 1
GLPK_LIB_DIR = '/usr/local/Cellar/glpk/4.60/lib'
GLPK_INC_DIR = '/usr/local/Cellar/glpk/4.60/include'


or the equivalent path on your machine. Then run the setup script as

python setup.py install


This will then allow CVXOPT to use the specific linear glpk solver.

Also useful:

• If you don’t care about the minimization output set

solvers.options[‘glpk’] = dict(msg_lev=’GLP_MSG_OFF’)

• For maximization, just realise that minimizing $- c^T \bar{x}$ is equivalent to maximizing $c^T \bar{x}$, to use the CVXOPT terms.

Categories:

Updated: