cvxopt не может решить простую линейную оптимизацию

у меня есть эта модель

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

где c — массив коэффициентов 16x1, G — матрица 12 x 16, представляющая ограничения модели, а h — массив единиц 12x1.

::::::::::::::
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

Из документации 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

в то время как использование интерфейса glpk cvxopt на самом деле работает гладко, и это дает мне хорошие решения:

(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 Solver работать в cvxopt для этой проблемы?


python optimization linear-programming cvxopt
person linello    schedule 30.07.2014    source источник
comment
Это может оказаться полезным. Кажется, что некоторые ограничения избыточны, и cvxopt этого не любит.   -  person Ioannis    schedule 30.07.2014
comment
Должен ли я каким-то образом понизить ранг G? Как?   -  person linello    schedule 31.07.2014
comment
Если действительно проблема в том, что предварительное решение не возвращает матрицу полного ранга, я бы просто использовал другой решатель.   -  person Ioannis    schedule 01.08.2014

Ответы (1)


arrow_upward
0
arrow_downward

Я не совсем уверен, но я думаю, что проблема больше математическая, чем основанная на коде.

Размеры ваших матриц: c равен 16 x 1, G равен 16 x 12 и h равен 12 x 1. Но ранг матрицы G намного ниже. На самом деле, на десять из 16 записей x ограничений нет. Для программы это невыполнимое решение, так как минимум будет минус бесконечность.

Например. для 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. Результат по-прежнему недостижим, но это может быть связано с ограничениями или какой-то другой ошибкой...

[Previous definition of the matrices]
>>> index = [1,2,3,6,7,11]
>>> c = c[index]
>>> G = G[::,index]
>>> cv.solvers.lp(c=c, G=G, h=h )
     pcost       dcost       gap    pres   dres   k/t
 0: -2.8000e-01 -1.3000e+01  1e+01  1e+00  5e+00  1e+00
 1: -1.7954e-01 -1.6503e+00  1e+00  1e-01  6e-01  7e-03
 2:  1.0328e-01 -1.5888e+01  1e+03  1e+00  6e+00  8e-01
 3: -1.1620e+01 -3.8498e+00  5e+03  3e-01  1e+00  1e+01
 4: -1.1605e+03 -3.8498e+00  5e+05  3e-01  1e+00  1e+03
 5: -1.1604e+05 -3.8498e+00  5e+07  3e-01  1e+00  1e+05
 6: -1.1604e+07 -3.8498e+00  5e+09  3e-01  1e+00  1e+07
 7: -1.1604e+09 -3.8498e+00  5e+11  3e-01  1e+00  1e+09
 Certificate of dual infeasibility found.
{'status': 'dual infeasible', 'dual slack': None, 'iterations': 7, 'residual as primal
infeasibility certificate': None, 'relative gap': None, 'dual objective': None, 
'residual as dual infeasibility certificate': 1.1035651154462114e-09, 'gap': None, 
's': <12x1 matrix, tc='d'>, 'primal infeasibility': None, 'dual infeasibility': None, 
'primal objective': -1.0, 'primal slack': 94.0289560690342, 'y': None, 'x': <6x1 
matrix, tc='d'>, 'z': None}

Не стесняйтесь поправить меня, если я ошибаюсь.

person Angela    schedule 31.07.2014
comment
Проблема в том, что проблема не является невыполнимой, поскольку GLPK действительно находит правильное решение. Так что я не понимаю, почему... - person linello; 01.08.2014