8.1 Linear Programming

lp( c, G, h[, A, b[, solver[, primalstart[, dualstart]]]])
Solves the pair of primal and dual LPs
\begin{displaymath}
\mbox{Primal:}\quad \begin{array}[t]{ll}
\mbox{minimize} & c...
...ubject to} & G^Tz + A^T y + c = 0 \\ & z \succeq 0.
\end{array}\end{displaymath} (8.1)

c, h and b are real single-column dense matrices. G and A are real dense or sparse matrices. The default values for A and b are sparse matrices with zero rows, meaning that there are no equality constraints.

The solver argument is used to choose among three solvers. When it is omitted or None, the default CVXOPT solver is used. The external solvers GLPK and MOSEK (if installed) can be selected by setting solver='glpk' or solver='mosek'; see section 8.8.

The optional arguments primalstart and dualstart are only referenced by the default solver. primalstart is a dictionary with keys 'x' and 's', used as an optional primal starting point. dualstart is a dictionary with keys 'y' and 'z', used as an optional dual starting point.

lp() returns a dictionary with keys 'status', 'x', 's', 'y', 'z'. The possible values of the 'status' item are as follows.

'optimal'.
In this case the 'x', 's', 'y' and 'z' entries contain the primal and dual solutions, which approximately satisfy

\begin{displaymath}
Gx + s = h, \qquad Ax=b, \qquad G^T z + A^T y + c = 0, \qquad
s \succeq 0, \qquad z \succeq 0, \qquad s^T z =0.
\end{displaymath}

'primal infeasible'.
The 'x' and 's' entries are None, and the 'y', 'z' entries provide an approximate certificate of infeasibility, i.e., vectors that approximately satisfy

\begin{displaymath}
G^T z + A^T y = 0, \qquad h^T z + b^T y = -1, \qquad z \succeq 0.
\end{displaymath}

With the 'glpk' option, no proof of infeasibility is returned (all entries of the dictionary are None).

'dual infeasible'.
The LP is dual infeasible. The 'y' and 'z' entries are None, and the 'x' and 's' entries contain an approximate certificate of dual infeasibility

\begin{displaymath}
Gx + s = 0, \qquad Ax=0, \qquad c^T x = -1, \qquad s \succeq 0.
\end{displaymath}

With the 'glpk' option, no proof of dual infeasibility is returned.

'unknown'.
The 'x', 's', 'y', 'z' entries are None.

As a simple example we solve the LP

\begin{displaymath}
\begin{array}[t]{ll}
\mbox{minimize} & -4x_1 - 5x_2 \\
\...
...2x_2 \leq 3 \\
& x_1 \geq 0, \quad x_2 \geq 0.
\end{array}
\end{displaymath}

>>> from cvxopt.base import matrix
>>> from cvxopt import 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.0000e-00
   1.0000e-00