An elegant way to represent and solve linear programming and other optimization problems in Python.

Note

This documentation is basically just a place holder until I have time to make it better

2009-02-16 08:18:04 UTC David Baird <dhbaird@gmail.com>

Version 0.1 release. Includes mixed-integer linear translation for GLPK and lp_solve. Provided quadratic programming translation for CVXOPT (but is missing integer translation capability, which I will try and do sometime later).

CVExp is short for "controlled vocabulary expressions." CVExp is a Python module that allows abstract syntax trees ("expressions") to be constructed just as easily as writing normal Python code. The names of functions in the abstract syntax trees are based on a controlled vocabulary, using URIs as names just like the W3C RDF does.

The intent of CVExp is that it should make it easier for developers to integrate 3rd party libraries into Python without having to specify entirely new APIs. Libraries and languages of particular concern are computer algebra systems, linear programming and optimization (such as lp_solve, GLPK, and CVXOPT), and Prolog.

Here is an example usage to solve a mixed-integer linear programming problem using GLPK as the backend. In order for this to work, you obviously must install prerequisite Python packages (i.e. python-glpk or whatever) because these are not included with CVExp:

from cvexp.builders import var from cvexp.builders import integer from cvexp.builders import minimize from cvexp.translate_glpk import solve # You could also use lp_solve by doing this: # from cvexp.translate_lpsolve55 import solve # ...or you could use CVXOPT like this: # from cvexp.translate_cvxopt import solve X = var('X') # the 'X' name is optional Y = var('Y') # ...and so is 'Y' # Purely linear programming: sol = solve(( Y + 0.1 == X, Y >= 9.8 - X, minimize(Y), ), out_filename='problem.out') # out_filename is optional print 'X =', sol[X] # >>> 4.95 print 'Y =', sol[Y] # >>> 4.85 # Mixed integer-linear programming: sol = solve(( Y + 0.1 == X, Y >= 9.8 - X, integer(Y), minimize(Y), ), out_filename='problem.out') # out_filename is optional print 'X =', sol[X] # >>> 5.1 print 'Y =', sol[Y] # >>> 5

If using CVXOPT, quadratic programming problems can also be solved. For example:

from cvexp.builders import var from cvexp.builders import integer from cvexp.builders import minimize from cvexp.translate_cvxopt import solve X = var() Y = var() sol = solve(( minimize((X - 5) ** 2 + (Y - 3) ** 2), )) print 'X =', sol[X] # >>> 5.0 print 'Y =', sol[Y] # >>> 3.0