使用线性规划绘制最长路径

Question

我有一个没有环的加权有向图，我希望定义约束，以便我可以使用线性规划解决路径权重的最大化问题。但是，我不知道该怎么做。

为此，我希望使用 LPSolve 工具。我考虑过制作邻接矩阵，但我不知道如何使用 LPSolve 实现它。

我如何使用约束定义每个节点的可能路径并使其足够通用以便很容易适应其他图？

Answer 1

因为你有一个加权有向图，为每条边 e 定义一个二进制变量 x_e 并添加指定源节点具有流量平衡 1 的约束就足够了（有选择的传出边比传入边多一条），目标节点的流量平衡为 -1（传入边比选中的传出边多一条），并且每个其他节点的流量平衡为 0（传出和传入边的数量相同）选中）。由于您的图表没有循环，因此这将导致从源到目的地的路径（假设存在）。您可以最大化所选边的权重。

我将继续使用 lpSolve 包在 R 中进行阐述。考虑具有以下边的图：

(edges <- data.frame(source=c(1, 1, 2, 3), dest=c(2, 3, 4, 4), weight=c(2, 7, 3, -4)))
#   source dest weight
# 1      1    2      2
# 2      1    3      7
# 3      2    4      3
# 4      3    4     -4

从 1 到 4 的最短路径是 1 -> 2 -> 4，权重为 5（1 -> 3 -> 4 的权重为 3）。

我们四个节点中的每一个都需要流量平衡约束：

source <- 1
dest <- 4
(nodes <- unique(c(edges$source, edges$dest)))
# [1] 1 2 3 4
(constr <- t(sapply(nodes, function(n) (edges$source == n) - (edges$dest == n))))
#      [,1] [,2] [,3] [,4]
# [1,]    1    1    0    0
# [2,]   -1    0    1    0
# [3,]    0   -1    0    1
# [4,]    0    0   -1   -1
(rhs <- ifelse(nodes == source, 1, ifelse(nodes == dest, -1, 0)))
# [1]  1  0  0 -1

现在我们可以将所有内容整合到我们的模型中并解决：

library(lpSolve)
mod <- lp(direction = "max", 
          objective.in = edges$weight,
          const.mat = constr,
          const.dir = rep("=", length(nodes)),
          const.rhs = rhs,
          all.bin = TRUE)
edges[mod$solution > 0.999,]
#   source dest weight
# 1      1    2      2
# 3      2    4      3
mod$objval
# [1] 5

使用线性规划绘制最长路径

Graph longest path using linear programming

optimization

graph

linear-programming

lpsolve

longest-path