routing - 单纯形法和网络单纯形法有什么区别？

Question

我正在使用网络 Simplex 来解决有向图中的最大流量问题。为了比较几种路由算法的执行时间，我需要使用 Dantzig 的单纯形方法 George 的实现。

我的问题是：单纯形法能否解决给定有向图中的最大流量问题？

是否有任何好的文档可以解释图论中的单纯形法？

Answer 1

网络单纯形法是一般单纯形法的一种高度专业化的形式：它只能解决网络问题。

当然，线性规划的标准 Simplex 方法也可以解决网络问题，只需将网络问题表述为 LP 问题。

为了比较，您可能想看看 Cplex：它都具有用于线性规划的（原始和对偶）Simplex 方法和 Network Simplex 方法的实现。

有趣的是，Gurobi 没有网络 Simplex 方法。这背后的想法是 LP 求解器变得如此之快，以至于专门的网络求解器已经失去了一些速度优势。

一个很好的参考资料是：Ahuja、Magnanti 和 Orlin，Network Flows。