CVXOPT and binary integer linear programming

[Carlo Nicolini]

I have this model

     min c' x
     s.t.
     G x <= h
     x are integers or binary variables

where `c` is a 16x1 numpy array of coefficients, `G` is a `12 x 16` matrix that represents the constraints of the model and `h` is 12x1 array of ones.

    ::::::::::::::
    c
    ::::::::::::::
    -0.00
    -0.38
    0.12
    0.12
    -0.38
    -0.00
    0.12
    0.12
    0.12
    0.12
    -0.00
    -0.38
    0.12
    0.12
    -0.38
    -0.00
    ::::::::::::::
    G
    ::::::::::::::
    0 1 -1 0 0 0 1 0 0 0 0 0 0 0 0 0
    0 1 1 0 0 0 -1 0 0 0 0 0 0 0 0 0
    0 -1 1 0 0 0 1 0 0 0 0 0 0 0 0 0
    0 1 0 -1 0 0 0 1 0 0 0 0 0 0 0 0
    0 1 0 1 0 0 0 -1 0 0 0 0 0 0 0 0
    0 -1 0 1 0 0 0 1 0 0 0 0 0 0 0 0
    0 0 1 -1 0 0 0 0 0 0 0 1 0 0 0 0
    0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0
    0 0 -1 1 0 0 0 0 0 0 0 1 0 0 0 0
    0 0 0 0 0 0 1 -1 0 0 0 1 0 0 0 0
    0 0 0 0 0 0 1 1 0 0 0 -1 0 0 0 0
    0 0 0 0 0 0 -1 1 0 0 0 1 0 0 0 0
    ::::::::::::::
    h
    ::::::::::::::
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1

From the cvxopt documentation I'd think that the model should be implemented as a linear program and be solved with lp solver

    cvxopt.solvers.lp(c=cvxopt.matrix(c), G=cvxopt.matrix(G), h=cvxopt.matrix(h) )

but I get this error:


    /usr/local/lib/python2.7/dist-packages/cvxopt/coneprog.pyc in lp(c, G, h, A, b, solver, primalstart, dualstart)
       3006
       3007     return conelp(c, G, h, {'l': m, 'q': [], 's': []}, A,  b, primalstart,
    -> 3008         dualstart)
       3009
       3010

    /usr/local/lib/python2.7/dist-packages/cvxopt/coneprog.pyc in conelp(c, G, h, dims, A, b, primalstart, dualstart, kktsolver, xnewcopy, xdot, xaxpy, xscal, ynewcopy, ydot, yaxpy, yscal)
        572     if kktsolver in defaultsolvers:
        573         if b.size[0] > c.size[0] or b.size[0] + cdim_pckd < c.size[0]:
    --> 574            raise ValueError("Rank(A) < p or Rank([G; A]) < n")
        575         if kktsolver == 'ldl':
        576             factor = misc.kkt_ldl(G, dims, A, kktreg = KKTREG)

    ValueError: Rank(A) < p or Rank([G; A]) < n

while using the glpk interface of cvxopt actually works smoothly and it gives me good solutions:

    (status, sol) = cvxopt.glpk.ilp(c=cvxopt.matrix(c),   # c parameter
                                    G=cvxopt.matrix(G),     # G parameter
                                    h=cvxopt.matrix(h),     # h parameter
                                    I=set(range(0, len(c))),
                                    B=set(range(0, len(c)))
                                    )

How can I make lp solver work in cvxopt for this problem?

[Martin]

CVXOPT's conelp solver assumes that G is full rank---this is clearly not the case here since the last four columns of G are zero. This means that the last four variables in x are free (since the conelp solver does not handle integer constraints), and hence the problem is unbounded. 

Try removing the last four variables from the problem and solve for these separately.