cvxopt不能解决简单的线性优化问题

Question

我有这个模型

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

其中c是一个16x1numpy的系数数组，G是表示模型约束的12 x 16矩阵，h是12x1的一个数组。在

^{pr2}$

根据cvxopt文档，我认为该模型应该作为一个线性规划来实现，并使用lp解算器进行求解

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

但我得到一个错误：

/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

而使用cvxopt的glpk接口，实际上工作很顺利，给了我很好的解决方案：

(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)))
                                )

如何使lp解算器在cvxopt中为这个问题工作？在

Answer 1

我不完全确定，但我认为，这个问题更多的是一个数学问题，而不是基于代码的问题。在

矩阵的维数是c是16 x 1，G是{}，而{}是{}。但矩阵G的秩要低得多。事实上，x的16个条目中有10个没有约束。负解是不可行的，因为它是不可行的。在

例如，x[14]在G和h中没有约束，它可以是任何值。在最小化函数c[14] = -0.38中，因此一个最小值将是x[14] = +inf，它给出了-inf = min c'x的解

以下是您描述的错误的解释：

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

这部分代码出现在不同的部分，通常检查问题的维度并确定是否有足够的约束来解决问题。在

我解决了这个问题，但忽略了x的任何无约束值。结果仍然不可行，但这可能是由于约束或其他错误。。。在

^{pr2}$

如果我错了，请随意纠正我。在