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

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