3

I'm considering using cvxopt to solve some nonlinear network flow optimisation problems. In order to understand the basics, I am trying it with a very simple test network with just 4 vertices and 5 edges.

My network looks like this. The blue and red nodes are a source and sink respectively.

The cost on each edge is:

alpha*x**2

where x is the vector containing the flow on each edge, and alpha is some coefficient. My optimisation problem is then:

     min sum(alpha*x**2)

subject to:

     E*x = b
     x >= 0

where E is the edge-arc incidence matrix and b is the vector containing sources and sinks. The matrix-vector equation Ex = b should therefore just enforce Kirchoff's laws (i.e. conservation of flow at each node).

My python script to do this is:

from cvxopt import matrix, spdiag, solvers

#Four vertices, five edges
E = matrix(0.0, (4,5))
E[0,0] = 1.0
E[0,1] = 1.0
E[1,0] = -1.0
E[1,2] = 1.0
E[1,3] = 1.0
E[2,1] = -1.0
E[2,2] = -1.0
E[2,4] = 1.0
E[3,3] = -1.0
E[3,4] = -1.0

#Source-sink vector
b = matrix(0.0, (4,1))
b[0] = 0.5
b[3] = -0.5

#Coefficient in the quadtratic
alpha = 1.0

#Function to pass to cvxopt
def F(x=None, z=None):

    if x is None:
        return 0, matrix(0.05, (5,1))
    if min(x) <= 0.0:
        return None

    f = sum(alpha*(x**2))
    Df = (2.0*alpha*x).T
    if z is None:
        return f, Df

    D2f = 2.0*alpha*matrix(1.0, (5,1))
    H = spdiag(z[0]*D2f)
    return f, Df, H

#Solve
x = solvers.cp(F, A=E, b=b)['x']

The error I get is:

     pcost       dcost       gap    pres   dres
 0:  0.0000e+00  1.2500e-02  1e+00  1e+00  2e-01
Traceback (most recent call last):
  File "simple_network.py", line 45, in <module>
    x = solvers.cp(F, A=E, b=b)['x']
  File "/usr/local/lib/python2.7/dist-packages/cvxopt/cvxprog.py", line 1966, in cp
    xdot_e, xaxpy_e, xscal_e, options = options)
  File "/usr/local/lib/python2.7/dist-packages/cvxopt/cvxprog.py", line 782, in cpl
    raise ValueError("Rank(A) < p or "\
ValueError: Rank(A) < p or Rank([H(x); A; Df(x); G]) < n

I am unsure how to proceed from here. I assumed this optimisation problem would be soluble with cvxopt, since it is simple enough to find the optimal flow by hand. I would appreciate it if somebody could tell me how to rectify this code, or else tell me why this type of problem is not suitable for this software.

Thanks in advance.

4

2 回答 2

1

今天遇到了同样的问题。

解决它的另一种方法是消除冗余约束。

取矩阵 E 的 SVD：

E = U S V'

S 与 E 具有相同的形状，最后一行将全为零（因为您的矩阵排名为 3）。

让y = V' x 和重新安排你的平等约束

E x = b
U S V' x = b
S V' x = U' b

的最后一行U' b必须为零，否则问题不可行。

设T为 的前 3 行S V'和c的前 3 行U' b。

然后你可以使用等式约束

T x = c

或者，使用 QR 分解cvxpy 做类似的事情

于 2019-07-01T23:06:31.757 回答
1

再想一想，我意识到这个问题是因为cvxopt要求矩阵在等式约束中的秩不小于等式约束的个数造成的。

在我的情况下，这意味着我的关联矩阵的秩必须等于网络中的节点数。然而，图论的一个结果是，任何具有 n 个节点的简单连通图都将具有秩为 n-1 的关联矩阵。这会产生秩误差。

我解决这个问题的方法是选择一个节点，并为其添加两条额外的边：一条从节点开始但无处可去，另一条从无处来并终止于节点。这实际上将两列添加到矩阵中。然后我在矩阵中添加了一行，要求这两条新边上的流量之和为零。

通过这种方式，我增加了矩阵的秩，而不添加任何额外的节点。原始网络上的流量不受添加这些边的影响，因为我要求新边上的流量保持为零。

这是一种有点笨拙的方法，但它似乎可以解决问题。

于 2017-05-09T17:10:48.817 回答