cvxopt CVXOPT glpk MILP的简单优化无优化

Question

我使用CVXOPT来解决这个简单的优化问题：

maximize X1 + X2 
s.t:
 X2 + X6      = 2
 X1 + X2 + X5 = 2
 X1 + X4      = 2
 X1           >=0
 X2           >=0 

显然，这有一个非常简单的解决方案。

 X1 = 1 
 X2 = 1 

(其余的都是0)

然而，cvxopt完全错了。我就是这样做的：

>>> print A
  [ 0.00e+00  1.00e+00  0.00e+00  0.00e+00  0.00e+00  1.00e+00]
  [ 1.00e+00  1.00e+00  0.00e+00  0.00e+00  1.00e+00  0.00e+00]
  [ 1.00e+00  0.00e+00  0.00e+00  1.00e+00  0.00e+00  0.00e+00]

>>> print b
[ 2.00e+00]
[ 2.00e+00]
[ 2.00e+00]

>>> print G
[-1.00e+00  0.00e+00  0.00e+00  0.00e+00  0.00e+00  0.00e+00]
[ 0.00e+00 -1.00e+00  0.00e+00  0.00e+00  0.00e+00  0.00e+00]

>>> print h
 [ 0.00e+00]
 [ 0.00e+00]

>>> print c
[-1.00e+00]
[-1.00e+00]
[ 0.00e+00]
[ 0.00e+00]
[ 0.00e+00]
[ 0.00e+00]

(以上都是cvxopt的“矩阵”类型)

打印glpk.ilp(c，G，h，A，b，I=set(0，1，2，3，4，5)1

GLPK Integer Optimizer, v4.43
5 rows, 6 columns, 9 non-zeros
6 integer variables, none of which are binary

Preprocessing...
3 rows, 5 columns, 7 non-zeros
5 integer variables, none of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 3
Solving LP relaxation...

GLPK Simplex Optimizer, v4.43

3 rows, 5 columns, 7 non-zeros
*     0: obj =   0.000000000e+00  infeas =  0.000e+00 (0)
PROBLEM HAS UNBOUNDED SOLUTION
None

Answer 1

下面是实现上述内容的代码：

import cvxopt.glpk
import cvxopt
c=cvxopt.matrix([1,1,0,0,0,0])
G=cvxopt.matrix([[1.0,0,0,0,0,0], [0,1,0,0,0,0]])
h=cvxopt.matrix([0.0,0.0])
A=cvxopt.matrix([[0.0,1,0,0,0,6], [1,1,0,0,1,0], [1,0,0,1,0,0]])
b=cvxopt.matrix([2.0, 2, 2])
(status, c)=cvxopt.glpk.ilp(-c,-(G.T),-h,A.T,b,I=set([0,1,2,3,4,5]))
print(status, c)

结果是：

optimal [ 0.00e+00]
[ 2.00e+00]
[ 0.00e+00]
[ 2.00e+00]
[ 0.00e+00]
[ 0.00e+00]

我不知道怎么找到所有的解决办法..。

Answer 2

根据您提供的LP，GLPK是正确的。

(0.5,0.5,1.5,1,1.5)是可行的

极端射线是(1,1，-1，-2，-1)。