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

Question

我有一个没有循环的加权有向图，我希望定义约束，以便我可以通过线性规划解决路径权重的最大化问题。但是，我无法解决如何做到这一点。

为此，我希望使用 LPSolve 工具。我曾想过制作一个邻接矩阵，但我不知道如何使用 LPSolve 来完成这项工作。

如何使用约束定义每个节点的可能路径，并使其足够通用，以便轻松适应其他图形？

Answer 1

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

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

(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