algorithm - 具有自定义成本函数的最小成本最大流量算法

Question

最小成本最大流量算法可以使用什么样的成本函数？

是否有可能具有类似于以下的成本函数：

• 如果边上的流在 [1, X] 之间，则成本 = FixedCost + C1 + flow * cost_per_flow[C1]
• 如果边上的流在 [X + 1, Y] 之间，则成本 = FixedCost + C2 + flow * cost_per_flow[C2]
• 等等

这会以任何方式改变算法吗？

Answer 1

您可以将固定成本相加，然后将其从等式中删除。然后，您将每条边分成 2 条边，每条边都有适当计算的成本。

Answer 2

最小成本最大流量算法只是特定类型线性程序的求解器。

使线性规划有效求解的是凸性：在这种情况下，如果您有两个可行的流 F 和 G，那么对于 [0, 1] 中的所有 t，流 tF + (1-t)G 是可行的并且具有成本（ tF + (1-t)G) ≤ t 成本(F) + (1-t) 成本(G)。对于您的目标，这基本上意味着 [1, X] 中的 FixedCost 为 0，C1 ≤ C2，[X + 1, Y] 中的 FixedCost 为 (C1 - C2)X ≤ 0。看起来像这样：

6|        .
5|       .
4|      .
3|     .
2|   .
1| .
0.----------
 0 1   X

对您来说，[1, X] > 0 中的 FixedCost 可能很重要，但这会使问题成为 NP 难题。图中的 Steiner 树的一个缩减是使每个边的容量无限，并花费由 Steiner 树问题为第一个单元指定的权重，然后为 0。使 k - 1 个 Steiner 终端中的一个成为容量为 k - 1 的源，其他为容量为 1 的接收器。请求最便宜的 k - 1 单位流量。