时间戳

首页 > 解决方案 > R中的网络流量平衡约束

r - R中的网络流量平衡约束

问题描述

我在 R 中开始处理最小成本流问题时有点迷失。在我看来，下面的限制是一个“经典”（输入总和减去输出总和等于供需向量），应该不难找到- 以稀疏表示法（我想避免像这里这样的转换矩阵：Minimum Cost Flow - network optimization in R）。我的问题是，如何在 R 中实现这种流量平衡限制，或者是否有我忽略的编码示例？

在此处输入图像描述

标签： rlinear-programming

解决方案

这是使用 igraph 和 Rsymphony 与稀疏矩阵（slam 包）的最小成本流示例：

鉴于此输入：

library(igraph)
nodes <- data.frame(name=paste0("N",1:8),
                    supply=c(10,20,0,-5,0,0,-15,-10))

edges <- data.frame(nodefrom = paste0("N",c( 1, 2, 2, 2, 3, 3, 4, 5, 5, 6, 7)),
                    nodeto   = paste0("N",c( 4, 1, 3, 6, 4, 5, 7, 6, 7, 8, 8)),
                    cost     = c( 2, 1, 0, 6, 1, 4, 5, 2, 7, 8, 9),
                    capacity = c(15,10,10,10, 5,10,10,20,15,10,15),
                    name     = paste0("E",1:11))
G <- graph.data.frame(edges)
V(G)$supply <- nodes$supply[match(V(G)$name,nodes$name)]
# plot the graph
set.seed(3)
par(mar=c(0,0,0,0))
plot(G, vertex.size=30,
     vertex.label=paste0(V(G)$name,' (',V(G)$supply,')'),
     vertex.color='lightblue', edge.arrow.size=0.5,
     edge.label=paste0(E(G)$name,' (',E(G)$cost,',',E(G)$capacity,')')
     )

输入图

library(Rsymphony)
library(slam)

nVars <- ecount(G)
obj <- E(G)$cost
bounds <- list(upper=list(1:nVars,E(G)$capacity),lower=list(1:nVars,rep(0,nVars)))
types <- rep('C',ecount(G))

mat <- simple_triplet_zero_matrix(nrow=nrow(nodes),ncol=nrow(edges))
colnames(mat) <- E(G)$name
rownames(mat) <- V(G)$name
rhs <- -V(G)$supply
dir <- rep('==',vcount(G))
for(v in V(G)){
  outEdges <- E(G)[from(v)]$name
  inEdges <- E(G)[to(v)]$name
  mat[v,match(inEdges,colnames(mat))] <- 1
  mat[v,match(outEdges,colnames(mat))] <- -1
}

output <- Rsymphony_solve_LP(obj=obj,
                   mat=mat,
                   dir=dir,
                   rhs=rhs,
                   bounds=bounds,
                   types=types,
                   max=FALSE,
                   write_lp = TRUE)

# plot the solution
set.seed(3)
par(mar=c(0,0,0,0))
plot(G, vertex.size=30,
     vertex.label=paste0(V(G)$name,' (',V(G)$supply,')'),
     vertex.color='lightblue', edge.arrow.size=0.5,
     edge.label=paste0(E(G)$name,' flow = ',output$solution))

输出图

关于稀疏矩阵，这里我们使用simple_triplet_zero_matrix它创建一个大小为 nrow x ncol 的全零矩阵（并且基本上不占用内存，因为在稀疏矩阵中只存储非零），然后我们用一些非零系数替换一些索引.

可能在大量输入的情况下，这可能不是很有效。
使用以下函数可能更有效，simple_triplet_matrix(i,j,v)其中i,j,v3 个相同长度的向量表示非零系数；特别i是行索引，j列索引和v位置的非零系数i,j。

推荐阅读