基于线性规划的图最小费用循环流问题的多项式时间缩放算法求解示例 1. 题目描述 我们考虑一个有向图 \( G = (V, E) \)，其中 \( V \) 是顶点集（\( |V| = n \)），\( E \) 是边集（\( |E| = m \)）。每一条边 \( e = (u, v) \in E \) 具有： 容量 \( u(e) > 0 \)（上界，表示允许流过的最大值）。 下界 \( l(e) \)（通常设为 0，但这里我们允许非负下界，即 \( 0 \le l(e) \le u(e) \)）。 单位流成本 \( c(e) \)（可以是任意实数，表示通过该边输送单位流量的成本）。 循环流（Circulation） 是一个函数 \( f: E \rightarrow \mathbb{R}^+ \) 满足： 容量约束 ：\( l(e) \le f(e) \le u(e) \) 对所有 \( e \in E \) 成立。 流量平衡 ：对于每个顶点 \( v \in V \)，流入的流量等于流出的流量，即： \[ \sum_ {e \in \delta^-(v)} f(e) = \sum_ {e \in \delta^+(v)} f(e) \] 其中 \( \delta^-(v) \) 是进入 \( v \) 的边集，\( \delta^+(v) \) 是离开 \( v \) 的边集。 最小费用循环流问题的目标是找到一个循环流 \( f \)，使得总成本 \( \sum_ {e \in E} c(e) f(e) \) 最小。 这是一个经典的网络流问题，可以通过转化为最小费用流问题并应用成本缩放算法来求解。本题将详细介绍基于容量和成本缩放的强多项式时间算法。 2. 解题思路 最小费用循环流问题可以直接建模为线性规划： \[ \begin{aligned} \min \quad & \sum_ {e \in E} c(e) f(e) \\ \text{s.t.} \quad & \sum_ {e \in \delta^+(v)} f(e) - \sum_ {e \in \delta^-(v)} f(e) = 0, \quad \forall v \in V, \\ & l(e) \le f(e) \le u(e), \quad \forall e \in E. \end{aligned} \] 这是一个具有特殊结构（网络矩阵是全单模矩阵）的线性规划，因此其基本可行解是整数（当所有 \( l(e), u(e) \) 为整数时）。求解该问题的经典算法包括 最小费用流算法 ，其中成本缩放算法（Cost Scaling）是强多项式时间的算法之一，时间复杂度为 \( O(m^2 \log n \cdot \log(nC)) \)，其中 \( C = \max_ {e} |c(e)| \)。我们将采用一种结合容量缩放和成本缩放思想的方法，确保解释清晰。 算法核心步骤： 问题转换 ：将下界非零的循环流问题转化为下界为0的最小费用流问题。 初始可行流的构建 ：通过引入人工变量或使用容量缩放初始化的方法获得一个初始可行循环流。 成本缩放优化 ：通过逐位降低成本精度，在每一缩放阶段通过解决一个“ε-最优”流问题来逼近最优解。 最优性条件与终止 ：基于 互补松弛条件 （或简化势函数的最优性条件）判断最优性，并在成本精度足够高时得到精确最优解。 3. 详细解题过程 步骤1：转化下界为非零的问题 如果存在边 \( e \) 满足 \( l(e) > 0 \)，我们可以进行如下转换以消除下界： 定义新的流量变量 \( f'(e) = f(e) - l(e) \)，则约束变为 \( 0 \le f'(e) \le u(e) - l(e) \)。 流量平衡约束会因此改变：对于每个顶点 \( v \)，净流出变化量为 \( b(v) = \sum_ {e \in \delta^+(v)} l(e) - \sum_ {e \in \delta^-(v)} l(e) \)。 问题转化为一个 最小费用流问题 ：在图中寻找流 \( f' \) 满足容量约束 \( 0 \le f'(e) \le u'(e) \) 和顶点供需约束 \( \sum_ {e \in \delta^+(v)} f'(e) - \sum_ {e \in \delta^-(v)} f'(e) = -b(v) \)，最小化 \( \sum c(e) f'(e) \)。注意这里 \( b(v) \) 的和必须为0（因为原问题可行），所以这是一个可行的流问题。 为简化，以下假设 \( l(e) = 0 \) 对所有 \( e \) 成立（即只有容量上界）。如果 \( l(e) \neq 0 \)，上述转换已隐含处理。 步骤2：构建初始可行循环流 由于是循环流，所有顶点供需为0。一个简单的初始可行流是零流：\( f(e) = 0 \) 对所有 \( e \)。这显然满足容量约束和平衡约束，但可能不是最小费用的。我们将从零流开始，通过成本缩放逐步优化。 步骤3：成本缩放算法框架 定义势函数 \( \pi: V \rightarrow \mathbb{R} \) 和约化成本（reduced cost）： \[ c^{\pi}(u, v) = c(u, v) + \pi(u) - \pi(v). \] 对于流 \( f \)，如果存在势 \( \pi \) 使得对所有边 \( (u, v) \) 满足以下 ε-互补松弛条件 ： 如果 \( c^{\pi}(u, v) > \varepsilon \)，则 \( f(u, v) = 0 \)（即正约化成本的边流量为0）。 如果 \( c^{\pi}(u, v) < -\varepsilon \)，则 \( f(u, v) = u(u, v) \)（即负约化成本的边流量为满容量）。 那么称流 \( f \) 是 ε-最优 的。 成本缩放算法 从一个大的 \( \varepsilon \) 值开始（例如 \( \varepsilon = C = \max |c(e)| \)），每次将 \( \varepsilon \) 减半（\( \varepsilon := \varepsilon / 2 \)），并在新的 \( \varepsilon \) 下通过调整流和势函数，使流重新满足 ε-最优条件，直到 \( \varepsilon < 1/n \)（因为所有数据是整数，此时 ε-最优流就是精确最优流）。 步骤4：单次缩放阶段（Refine） 给定当前流 \( f \) 和势 \( \pi \) 满足 ε-最优条件，我们要将其转化为 (ε/2)-最优。具体操作： 更新势函数：令 \( \pi'(v) = \pi(v) \) 初始保持不变。 在约化成本 \( c^{\pi'}(e) \) 下考虑边。由于 \( \varepsilon \) 减半，原来满足 ε-最优条件的边可能不再满足 (ε/2)-最优。我们需要调整流，使所有边满足新的更严格的条件。 调整方法： 通过解决一系列最短增广路问题 。具体地，考虑残差网络 \( G_ f \)（对于每条边 \( e = (u,v) \)，如果 \( f(e) < u(e) \) 则有一条正向边 \( (u,v) \) 残差容量为 \( u(e) - f(e) \)，成本为 \( c^{\pi'}(e) \)；如果 \( f(e) > 0 \) 则有一条反向边 \( (v,u) \) 残差容量为 \( f(e) \)，成本为 \( -c^{\pi'}(e) \)）。 在残差网络中，如果存在一条路径从 \( s \) 到 \( t \) 的路径上所有边的约化成本都小于0，则沿该路径增流可以降低总成本。但这里由于是循环流，没有源汇，我们通过 引入“超额”顶点 来处理：实际上，在缩放阶段，我们维护一组顶点有正超额（流入 > 流出）和负超额（流出 > 流入），然后通过推送从正超额顶点到负超额顶点的最短路径（按约化成本）上的流来平衡超额，同时保持 (ε/2)-最优性。 更常用的实现是采用 push-relabel 风格的成本缩放算法 （也称为“成本缩放-超额缩放算法”），它在每个阶段对每个超额顶点进行“推送”操作（沿着约化成本为负的边推送流）和“重标”操作（调整势函数以使约化成本非负），直到所有顶点超额为0。 步骤5：算法伪代码概览 由于详细代码较长，这里给出高层描述： 输入：图 \( G=(V,E) \)，容量 \( u(e) \)，成本 \( c(e) \) 输出：最小费用循环流 \( f \) 初始化：设 \( f = 0 \)（零流），\( \pi = 0 \)，\( \varepsilon = C \)。 当 \( \varepsilon \ge 1/n \) 执行： a. \( \varepsilon := \varepsilon / 2 \)。 b. 对每条边 \( e \)，如果 \( |c^{\pi}(e)| > \varepsilon \) 且当前流不满足 (ε/2)-最优条件，则通过调整流使其满足。具体调整通过一个 改进过程 实现，该过程反复选择超额顶点，并沿约化成本为负的边推送流，直到无法继续，然后更新该顶点的势函数（增加 \( \varepsilon/2 \)），重复直到所有顶点超额为0。 返回 \( f \)。 步骤6：最优性验证与复杂度 最终当 \( \varepsilon < 1/n \) 时，流 \( f \) 是 0-最优的，即满足精确的互补松弛条件，因此是最优解。算法运行时间为 \( O(m^2 \log(nC)) \) 或经优化可达到 \( O(mn \log n \cdot \log(nC)) \)。由于每次缩放 ε 减半，缩放次数为 \( O(\log(nC)) \)，每次缩放内 push-relabel 风格的操作次数为 \( O(mn) \) 或 \( O(m^2) \)。 4. 实例演示（简化） 考虑一个小图：\( V = \{1,2,3\} \)，边 \( E = \{(1,2), (2,3), (3,1)\} \)，所有边容量 \( u = 5 \)，成本 \( c(1,2)=3, c(2,3)=-2, c(3,1)=1 \)。目标是找到最小费用循环流。 初始：\( f=0, \pi=0, \varepsilon=3 \)（因为 \( C=3 \)）。 第一次缩放：\( \varepsilon=1.5 \)。 检查边 (1,2)：\( c^{\pi}=3 > 1.5 \)，ε-最优要求若 \( c^{\pi} > \varepsilon \) 则 \( f=0 \)，满足。 边 (2,3)：\( c^{\pi}=-2 < -1.5 \)，要求 \( f=5 \)，但当前 \( f=0 \) 不满足，需要调整。 调整：在残差图中，从顶点2到3存在正向边 (2,3) 约化成本 -2，可增流。将流增加到5（满容量），此时顶点2超额 -5（流出太多），顶点3超额 +5（流入太多）。为了保持循环，需要通过其他边平衡。在 (3,1) 上增流5（成本1），然后在 (1,2) 上增流5（成本3）。总成本变化：\( 5* (-2+1+3)=10 \)。调整后 \( f(2,3)=5, f(3,1)=5, f(1,2)=5 \)，是一个循环流，总成本 \( 5* (-2+1+3)=10 \)。 更新势函数使得满足 (ε/2)-最优条件（具体计算略，通常通过重标实现）。 继续缩放直到 \( \varepsilon < 1/3 \)，最终得到最优流。本例中上述流已是最优（因为负成本边已满容量，正成本边流量可调整但会破坏平衡，检查互补松弛条件可知最优）。 5. 总结 本题通过成本缩放算法求解最小费用循环流问题，展示了如何将线性规划问题转化为网络流问题，并利用其特殊结构设计强多项式时间算法。关键在于理解 ε-最优条件、势函数和约化成本的作用，以及通过缩放逐步逼近最优解的过程。这种方法结合了线性规划的对偶理论（势函数相当于对偶变量）和组合优化中的高效算法设计思想，是处理大规模网络流问题的有效工具。