基于线性规划的图最大流问题的多项式时间原始-对偶算法求解示例
1. 问题描述
给定一个有向图 \(G = (V, E)\)，其中 \(V\) 是顶点集合，\(E\) 是边集合。图中有两个特殊顶点：源点 \(s \in V\) 和汇点 \(t \in V\)。每条边 \(e \in E\) 有一个非负的容量 \(c(e) \geq 0\)。一个“流”是一个从 \(E\) 到非负实数的函数 \(f: E \to \mathbb{R}_{\geq 0}\)，它满足以下两个约束：
- 容量约束：对于每条边 \(e\)，有 \(0 \leq f(e) \leq c(e)\)。
- 流量守恒：对于每个顶点 \(v \in V \setminus \{s, t\}\)，流入 \(v\) 的总流量等于流出 \(v\) 的总流量，即：
\[ \sum_{e=(u,v) \in E} f(e) = \sum_{e=(v,w) \in E} f(e) \]
（这里 $ e=(u,v) $ 表示一条从 $ u $ 指向 $ v $ 的边）。
最大流问题的目标是，在满足上述所有约束的前提下，最大化从源点 \(s\) 发出的净流量（或流入汇点 \(t\) 的净流量），这个值称为流 \(f\) 的“流量值” \(|f|\)。
今天我们要讲的，不是Ford-Fulkerson或Push-Relabel等经典组合算法，而是从线性规划（LP）的角度，通过构造一个精心设计的“原始-对偶”算法来解决最大流问题。这个算法被称为Garg-Könemann框架在最大流问题上的一个具体应用，它能证明最大流问题可以在多项式时间内通过原始-对偶方法求解。我们的核心是通过求解一个分数打包线性规划的对偶问题，来逐步逼近最大流。
2. 数学模型构建
2.1 原始线性规划（分数多商品流视角）
虽然标准的单一商品最大流可以直接建模为一个线性规划，但为了应用我们的原始-对偶框架，我们采用一个等价的、但更结构化的建模方式：路径流模型。
设 \(P\) 为从源点 \(s\) 到汇点 \(t\) 的所有简单路径的集合。对于每条路径 \(p \in P\)，我们定义一个决策变量 \(f_p\)，表示流经路径 \(p\) 的流量。
原始问题（P）：
\[\begin{aligned} \max \quad & \sum_{p \in P} f_p \\ \text{s.t.} \quad & \sum_{p: e \in p} f_p \leq c(e), \quad \forall e \in E \quad \text{(容量约束)} \\ & f_p \geq 0, \quad \forall p \in P \end{aligned} \]
- 目标函数：最大化从 \(s\) 到 \(t\) 的总流量。
- 约束条件：对于每条边 \(e\)，所有经过它的路径上的流量之和不能超过该边的容量。
- 这个规划是等价的，但变量数（路径数）是指数级的。我们不会显式地列出所有路径。
2.2 对偶线性规划
为原始问题（P）引入对偶变量 \(y_e\) 对应于每条边 \(e\) 的容量约束。
对偶问题（D）：
\[\begin{aligned} \min \quad & \sum_{e \in E} c(e) y_e \\ \text{s.t.} \quad & \sum_{e \in p} y_e \geq 1, \quad \forall p \in P \quad \text{(路径长度约束)} \\ & y_e \geq 0, \quad \forall e \in E \end{aligned} \]
- 变量 \(y_e\) 可以理解为边 \(e\) 的“长度”或“价格”。
- 约束条件：对于每条从 \(s\) 到 \(t\) 的路径 \(p\)，其边的“长度”之和至少为1。这可以理解为，任何一条可行路径的成本（长度）不低于1。
- 目标函数：最小化所有边的“总加权长度”（容量乘以长度）。
根据线性规划强对偶定理，如果原始和对偶都有可行解，则它们的最优值相等。最大流的值等于最小割的值（最大流最小割定理），而在这个对偶模型中，最小割对应着一个满足对偶约束的、能“阻挡”所有路径的、最小容量的边集分配方案。实际上，一个(0-1)的 \(y_e\) 对应于一个割，分数 \(y_e\) 是它的推广。
3. 原始-对偶算法设计思想
直接求解（P）和（D）是困难的，因为路径集合 \(P\) 太大。原始-对偶算法的核心思想是：在不知道所有路径的情况下，通过迭代地求解一个“限制性的”对偶问题，并利用其解来生成能改善原始目标函数的路径（即原始变量）。
我们将采用一个基于“乘子更新”的算法框架，类似于分数打包问题的求解方法。
算法步骤详解
初始化：
- 设置初始对偶变量（边长度）：\(y_e^{(0)} = \delta / c(e)\)，对于所有 \(e \in E\)。其中 \(\delta \in (0,1)\) 是一个很小的正参数，例如 \(\delta = (1+\epsilon)^{-1}\) 或与 \(|E|\) 相关的函数，它的作用是初始长度与容量成反比，确保算法从一个小规模开始。同时设定一个精度参数 \(\epsilon > 0\)。
- 初始化原始流：\(f_p = 0\) 对于所有路径 \(p\) （实际上我们不需要存储所有路径，只需要记录每条边上的总流量 \(F(e) = 0\) 和总流量值 \(Flow = 0\)）。
- 设置对偶目标值：\(D^{(0)} = \sum_{e} c(e) y_e^{(0)}\)。
迭代过程（当对偶目标值 \(D^{(k)} < 1\) 时继续循环，因为对偶可行解的目标值需要 ≥1 才能满足某些路径约束，这里我们是在寻找近似对偶解）：
步骤1：计算最短路径
在当前边长度 \(\{y_e^{(k)}\}\) 下，使用Dijkstra等最短路径算法，计算从源点 \(s\) 到汇点 \(t\) 的最短路径 \(p^{(k)}\)（按长度求和）。设其路径长度为 \(L^{(k)} = \sum_{e \in p^{(k)}} y_e^{(k)}\)。
步骤2：检查终止条件（近似对偶可行性）
如果 \(L^{(k)} \geq 1\)，说明当前的长度分配 \(\{y_e^{(k)}\}\) 使得 所有 \(s-t\) 路径长度都至少为1（因为最短的都已经≥1）。那么，\(\{y_e^{(k)}\}\) 是对偶问题（D）的一个可行解。此时算法可以进入最后一步的缩放和输出阶段。否则，继续步骤3。
步骤3：更新原始流（沿最短路径发送流）
选择路径 \(p^{(k)}\) 上剩余容量最小的边，设其剩余容量为 \(\gamma = \min_{e \in p^{(k)}} (c(e) - F(e))\)。沿着路径 \(p^{(k)}\) 发送 \(\gamma\) 单位的流量。即：
- 更新边流量：对于所有 \(e \in p^{(k)}\)，\(F(e) := F(e) + \gamma\)。
- 更新总流量：\(Flow := Flow + \gamma\)。
(注意：实际上，为了确保多项式时间，我们通常会发送一个更小的、固定的流量单位，比如 \(\theta = \min(\gamma, \alpha)\)，其中 \(\alpha\) 是一个小常数，或者采用连续增加的方式。但在概念上，发送路径上的瓶颈容量是核心思想。一个更严格的实现是每次发送固定量 \(\Delta\)，使得对偶变量更新可控。)
步骤4：更新对偶变量（增加“拥堵”边的长度）
对于我们刚刚发送了流量的路径 \(p^{(k)}\) 上的每一条边 \(e\)，增加其长度。增量的设计原则是：边被使用的频率越高（越拥堵），其“价格”或“长度”增长得越快。一个标准更新公式是：
\[y_e^{(k+1)} := y_e^{(k)} \cdot (1 + \frac{\epsilon \cdot \gamma}{c(e)}) \]
如果流量发送单位是固定的 \(\theta\)，则公式为 \(y_e^{(k+1)} := y_e^{(k)} \cdot (1 + \frac{\epsilon \cdot \theta}{c(e)})\)。
- 解释：\(\frac{\gamma}{c(e)}\) 是本次发送流量占该边容量的比例。比例越大，说明该边越接近饱和，其长度增加越多。因子 \((1+\epsilon)\) 确保了多项式时间的收敛性。
- 对于不在 \(p^{(k)}\) 上的边，其长度保持不变：\(y_e^{(k+1)} := y_e^{(k)}\)。
步骤5：更新对偶目标值并循环
重新计算当前的对偶目标值 \(D^{(k+1)} = \sum_{e \in E} c(e) y_e^{(k+1)}\)。
检查循环条件 \(D^{(k+1)} < 1\) 和 \(L^{(k+1)} < 1\) （或者设置最大迭代次数）。返回步骤1。
最终缩放与输出：
当算法终止（即找到一组使得最短路径长度 \(L \geq 1\) 的对偶变量 \(\{y_e\}\)）时，我们得到了：
- 原始解：一个可行的流 \(F(e)\) 和总流量 \(Flow\)。
- 对偶解：一组对偶变量 \(\{y_e\}\) 满足 \(\sum_{e \in p} y_e \geq 1\) 对于所有路径 \(p\) 成立。
根据弱对偶定理，对于任何原始可行流 \(f\) 和对偶可行解 \(y\)，有：
\[\sum_{p} f_p \leq \sum_{e} c(e) y_e \]
在我们的算法中，我们有一个原始流 \(F\) （对应 \(\sum_p f_p = Flow\)）和一个对偶解 \(y\)。但请注意，我们的对偶解是在算法结束时才满足可行性，而原始流是在整个过程中累积的。为了得到一个严格的理论保证，我们需要证明：
\[Flow \geq (1 - O(\epsilon)) \cdot \sum_{e} c(e) y_e \]
通过仔细选择参数 \(\delta, \epsilon\) 和更新公式中的乘子，可以证明最终的 \(Flow\) 是最大流的 \((1-\epsilon)\) 近似，并且算法总迭代次数是 \(|E| \cdot (1/\epsilon)^2 \cdot \log(|E|)\) 的多项式级别。
最终，算法输出计算得到的流 \(\{F(e)\}\) 作为原最大流问题的近似最优解。
4. 算法核心要点总结
- 原始-对偶互动：算法在原始空间（发送流量）和对偶空间（调整边长度）之间交替进行。
- 最短路径作为“最违反约束”：在每一步，当前最短的 \(s-t\) 路径对应了对偶问题中“最可能被违反”的约束（因为它的长度小于1）。我们通过在这条路径上发送流量来尝试“满足”这个约束（实质上是让使用这条路径的边变贵，增加其长度，从而未来不再是最短）。
- 长度更新机制：边长度按指数增长，与流量使用率成正比。这类似于一种“协调障碍法”，防止流量过度集中在少数边上，鼓励流分散到不同路径，从而更有效地利用网络容量。
- 多项式时间：通过精心的参数设置（\(\delta, \epsilon\) 和更新公式），可以确保算法在多项式时间内收敛到一个 \((1-\epsilon)\) 近似的最优解。
这个算法不仅提供了求解最大流问题的一种新视角，更重要的是，它展示了如何将原始-对偶方法应用于具有指数级约束的线性规划问题，并通过迭代地解决“限制性主问题”来获得近似最优解。这是组合优化中近似算法设计的一个强大范式。