7.3 Linear Programming

The function lp() is an interface to conelp() for linear programs. It also provides the option of using the linear programming solvers from GLPK or MOSEK.

lp(c, G, h[, A, b[, solver[, primalstart[, dualstart]]]])

Solves the pair of primal and dual linear programs

           T                              T    T
minimize   c x                maximize  - hT z - bT y
subject to Gx + s = h         subject to G  z + A y+ c = 0
          Ax = b                       z ≽ 0.
          s ≽ 0

The inequalities are componentwise vector inequalities.

The solver argument is used to choose among three solvers. When it is omitted or None, the CVXOPT function conelp() is used. The external solvers GLPK and MOSEK (if installed) can be selected by setting solver = ’glpk’ or solver = ’mosek’; see section 7.8. The meaning of the other arguments and the return value are the same as for conelp() called with dims = {’l’: G.size[0], ’q’: [], ’s’: []}.

The initial values are ignored when solver ’mosek’ or ’glpk’. With the GLPK option, the solver does not return certificates of primal or dual infeasibility: if the status is ’primal infeasible’ or ’dual infeasible’, all entries of the output dictionary are None. If the GLPK or MOSEK solvers are used, and the code returns with status ’unknown’, all the other fields in the output dictionary are None.

As a simple example we solve the LP

minimize   - 4x1 - 5x2
subject to 2x1 + x2 ≤ 3
           x1 + 2x2 ≤ 3
           x1 ≥ 0, x2 ≥ 0.

>>> from cvxopt import matrix, solvers  
>>> c = matrix([-4., -5.])  
>>> G = matrix([[2., 1., -1., 0.], [1., 2., 0., -1.]])  
>>> h = matrix([3., 3., 0., 0.])  
>>> sol = solvers.lp(c, G, h)  
>>> print sol[’x’]  
[ 1.00e+00]  
[ 1.00e+00]