基于线性规划的图最小环覆盖问题的分数线性规划松弛与舍入算法求解示例
一、问题描述
我们考虑一个经典的图论优化问题——图的最小环覆盖问题。给定一个有向图 \(G = (V, E)\)，其中每条边 \(e \in E\) 有一个非负的权重 \(w(e)\)（通常可以代表距离、成本或时间）。一个环覆盖 是一组有向环（可能包含长度为2的环，即一条边来回走，但通常要求覆盖所有顶点），使得图 \(G\) 中的每个顶点恰好出现在其中一个环中。最小环覆盖问题的目标是找到一个环覆盖，使得所有环的边权重总和最小。
这个问题在运筹学和组合优化中有重要应用，例如：
- 车辆路径规划：将客户点（顶点）分配给若干条车辆路线（环），每辆车从仓库出发访问若干客户后返回仓库，要求总行驶距离最短。
- 任务调度与排序：将任务分配到多个机器或处理器上，每个处理器上的任务构成一个处理循环。
最小环覆盖问题可以表述为整数线性规划问题。然而，直接求解整数规划是NP难的（因为它等价于非对称旅行商问题的松弛版本）。因此，一个常见的精确算法思路是：先求解其线性规划松弛，得到一个分数最优解，然后设计舍入算法，将其转化为一个合法的整数解（即环覆盖），并分析该整数解与最优解之间的近似比。
二、数学模型构建
2.1 整数线性规划模型
对于每条有向边 \(e = (u, v) \in E\)，我们引入一个二元决策变量 \(x_e\)：
- \(x_e = 1\) 表示边 \(e\) 被选中包含在某个环中；
- \(x_e = 0\) 表示边 \(e\) 未被选中。
目标函数：最小化总权重。
\[\min \sum_{e \in E} w(e) x_e \]
约束条件：
- 每个顶点的出度恰好为1（因为每个顶点必须恰好是一条出边的起点，从而保证每个顶点被一个环覆盖且仅被一个环覆盖）：
\[ \sum_{v: (u, v) \in E} x_{(u, v)} = 1, \quad \forall u \in V \]
- 每个顶点的入度恰好为1（类似地，保证每个顶点恰好是一条入边的终点）：
\[ \sum_{v: (v, u) \in E} x_{(v, u)} = 1, \quad \forall u \in V \]
- 消除子环约束（防止解由多个不相交的小环构成，我们希望它是一个单环吗？不！在最小环覆盖中，解可以包含多个环，但每个环必须覆盖至少两个顶点吗？没有这个要求。实际上，上述两个约束本身已经允许长度为1的自环（如果存在）或长度为2的环，但通常我们假设没有自环，且允许长度为2的环。然而，如果不加额外约束，上述约束的解可能是多个不相交的有向环的集合，这正是我们想要的“环覆盖”的定义。因此，约束1和2已经定义了环覆盖的整数解集合。所以，不需要额外的消除子环约束。这正是该问题与旅行商问题的区别：旅行商问题要求一个哈密顿圈，因此需要消除子环；而环覆盖允许多个环，所以不需要消除子环约束。但等等，这样整数规划的最优解会不会就是一组完美的匹配（即每个顶点和自己形成一个长度为2的环，如果存在这样的边）？不一定，因为每条边可能有不同的权重。因此，整数规划模型就是上述目标函数和约束1、2，以及 \(x_e \in \{0,1\}\)。）
但是，这个整数规划模型存在一个问题：如果直接去掉整数约束 \(x_e \in \{0,1\}\)，改为 \(0 \leq x_e \leq 1\)，得到的线性规划松弛的最优解可能不是整数解，而是一组分数值。我们称这个松弛为分数线性规划松弛。
2.2 分数线性规划松弛模型
\[\begin{aligned} \min & \sum_{e \in E} w(e) x_e \\ \text{s.t.} & \sum_{v: (u, v) \in E} x_{(u, v)} = 1, \quad \forall u \in V \\ & \sum_{v: (v, u) \in E} x_{(v, u)} = 1, \quad \forall u \in V \\ & 0 \leq x_e \leq 1, \quad \forall e \in E \end{aligned} \]
注意：这里我们不需要显示地写出 \(x_e \leq 1\)，因为从出度和入度约束（每个和为1）以及非负性可推出 \(x_e \leq 1\)。但为了清晰，可以保留。
这个线性规划是一个指派问题的线性规划形式，但它是在一个一般有向图上，而不是完全二分图。当图 \(G\) 是完全有向图（即每对顶点间有两条方向相反的边）时，该线性规划就是经典的指派问题的线性规划。我们知道，指派问题的系数矩阵是全幺模的，因此其线性规划的最优解自动是整数解。然而，对于一般的有向图，系数矩阵可能不是全幺模的，因此线性规划的最优解可能是分数解。
三、算法设计与步骤
我们的算法分为两步：
- 求解分数线性规划松弛，得到最优分数解 \(x^*\)。
- 舍入分数解，得到一个整数解（即一个环覆盖），并证明其权值不超过分数最优解的某个倍数。
3.1 求解分数线性规划松弛
我们可以使用任何线性规划求解器（例如单纯形法、内点法）来求解上述LP。假设我们得到了最优解 \(x^* = \{ x_e^* \}_{e \in E}\)，且 \(0 \leq x_e^* \leq 1\)。设 \(OPT_f = \sum_{e \in E} w(e) x_e^*\) 为分数最优值。显然，\(OPT_f \leq OPT\)，其中 \(OPT\) 是原整数规划的最优值（即最小环覆盖的真实最小权值）。
3.2 分数解的结构分析
解 \(x^*\) 满足：对每个顶点 \(u\)，其出边上的 \(x^*\) 值之和为1，入边上的 \(x^*\) 值之和也为1。这可以看作是在图 \(G\) 上定义了一个分数环覆盖：每个顶点分配了1个单位的“流出流”和1个单位的“流入流”，且流在边上以分数形式存在。
我们可以将 \(x^*\) 视为一个有向图 \(G\) 上的循环流（circulation），因为每个顶点的净流量为0（出流和=入流和）。这样的循环流可以分解为若干有向环（cycle）上的流，每个环被赋予一个流值，且这些流值之和为1（对于每个顶点，包含它的所有环的流值之和为1）。更准确地说，根据流分解定理，我们可以将 \(x^*\) 写成：
\[x^* = \sum_{C \in \mathcal{C}} \lambda_C \chi^C \]
其中 \(\mathcal{C}\) 是图 \(G\) 中所有有向环的集合，\(\lambda_C \geq 0\) 是环 \(C\) 的权重，\(\chi^C\) 是环 \(C\) 的指示向量（即如果边 \(e\) 在环 \(C\) 中，则 \(\chi^C_e = 1\)，否则为0）。并且满足对于每个顶点 \(u\)：
\[\sum_{C: u \in C} \lambda_C = 1 \]
同时，总权重 \(\sum_{C} \lambda_C w(C) = OPT_f\)，其中 \(w(C) = \sum_{e \in C} w(e)\)。
这个分解可以通过在图 \(x^*\) 上不断寻找有向环并抽取流来实现，直到所有边上的流被分解完毕。因为 \(x^*\) 是分数值，分解出的环数量可能是指数级的，但我们可以不显式地枚举所有环，而是利用分解的概念来指导舍入。
3.3 基于循环流舍入的算法
一个经典的舍入策略是随机化舍入，我们按照一定概率随机选择环。具体步骤如下：
算法：随机化舍入
- 对分数解 \(x^*\) 进行循环流分解，得到一组环 \(\mathcal{C}\) 及其对应的权重 \(\lambda_C\)（满足 \(\sum_{C: u \in C} \lambda_C = 1\) 对每个顶点 \(u\)）。
- 随机选择环：以概率 \(\lambda_C\) 独立地选择环 \(C\)（注意：这里 \(\lambda_C\) 可能很多，且和不一定为1，因为每个环可能覆盖多个顶点，所有环的 \(\lambda_C\) 之和可能大于1）。实际上，我们需要一个更精细的舍入方法，因为直接以 \(\lambda_C\) 独立选择环可能导致顶点被多个环覆盖或不被任何环覆盖。
我们需要一个保证每个顶点恰好被一个环覆盖的舍入方法。这可以通过以下方式实现：
改进的舍入方法（基于匹配的舍入）：
观察分数解 \(x^*\) 构成的矩阵 \((x_{uv}^*)_{u,v \in V}\)（如果边 \((u,v)\) 不存在，则 \(x_{uv}^* = 0\)）。这个矩阵是一个双随机矩阵（所有行和与列和均为1）。根据Birkhoff-von Neumann定理，任何双随机矩阵都可以表示为排列矩阵的凸组合。排列矩阵对应一个完美匹配（在有向图中，一个排列对应一个环覆盖，每个环是一个置换环）。即：
\[x^* = \sum_{k=1}^K \theta_k P^k \]
其中 \(P^k\) 是排列矩阵（即每行每列恰好一个1，其余为0），\(\theta_k > 0\)，且 \(\sum_{k=1}^K \theta_k = 1\)。每个排列矩阵 \(P^k\) 对应一个环覆盖（可能包含多个环，因为排列可以分解为循环置换）。注意，这个分解中的每个 \(P^k\) 就是一个整数解（环覆盖）。
因此，我们可以利用这个分解进行随机舍入：
- 以概率 \(\theta_k\) 选择排列 \(P^k\)（即环覆盖）作为我们的整数解。
由于我们按照概率 \(\theta_k\) 选择，所得到的整数解 \(\tilde{x}\) 的期望权重为：
\[\mathbb{E}[ \sum_{e} w(e) \tilde{x}_e ] = \sum_{k} \theta_k \sum_{e} w(e) P^k_e = \sum_{e} w(e) \sum_{k} \theta_k P^k_e = \sum_{e} w(e) x_e^* = OPT_f \]
因此，期望权重等于分数最优值 \(OPT_f\)。由于 \(OPT_f \leq OPT\)，我们得到期望权重不超过 \(OPT\)。这是一个随机化1-近似算法（在期望意义下）。
然而，我们可能想要一个确定性的算法，或者一个具有常数近似比的确定性算法。我们可以使用条件期望法去随机化，从而得到一个确定性算法，其权重不超过 \(OPT_f\)，但时间复杂度较高（需要分解双随机矩阵并计算条件期望）。另一种方法是直接利用双随机矩阵的分解，然后选择其中权重最小的那个排列 \(P^k\)，由于权重是凸组合，最小权重的排列的权重不超过 \(OPT_f\)，因此这也是一个1-近似算法（但需要枚举所有排列，分解中排列数量可能指数多，不现实）。
在实践中，我们可以使用近似舍入方法，例如：
- 使用二分图匹配舍入：将问题转化为二分图最小权完美匹配问题。具体地，构造二分图 \(H = (U, V, E')\)，其中 \(U\) 和 \(V\) 都是原图顶点集 \(V\) 的拷贝。对于原图中的每条边 \((u,v)\)，在二分图中添加边 \((u, v)\)（连接 \(U\) 中的 \(u\) 到 \(V\) 中的 \(v\) ），权重为 \(w(u,v)\)。那么，原问题的分数线性规划松弛正是这个二分图上的指派问题的线性规划。我们知道，二分图指派问题的线性规划整数性成立（因为系数矩阵是全幺模的），因此其最优解是整数解，即一个完美匹配。这个完美匹配对应原图的一个环覆盖（每个匹配边对应原图的一条有向边，而完美匹配在二分图中对应一个置换，即原图的一个环覆盖）。因此，如果我们求解的是二分图上的指派问题线性规划，我们直接得到整数最优解。
但是，注意：我们的原图 \(G\) 可能不是完全二分图，因此当我们将原问题建模为二分图指派问题时，如果原图中缺少某些边，我们在二分图中也不添加对应的边，那么二分图可能没有完美匹配，这样原问题就没有可行解。然而，原问题要求环覆盖，如果原图不连通或者某些顶点没有出边或入边，环覆盖可能不存在。我们通常假设原图存在环覆盖（例如，图是强连通的，或者至少每个顶点都有出边和入边）。在算法中，我们可以先检查是否存在完美匹配，如果不存在，则原问题无解。
因此，总结算法：
- 构造二分图 \(H\)：左部 \(U\) 和右部 \(V\) 均为原顶点集 \(V\) 的拷贝。对于原图中的每条有向边 \((u,v)\)，在 \(H\) 中添加边 \((u \in U, v \in V)\) 权重为 \(w(u,v)\)。
- 在二分图 \(H\) 上求解最小权完美匹配问题（即指派问题）。可以使用匈牙利算法（对于稠密图）或者网络流算法（例如最小费用最大流）。
- 得到的最优完美匹配 \(M\) 对应原图的一个环覆盖：将匹配边 \((u,v)\) 映射回原图的有向边 \((u,v)\)，这些边构成一组有向环（因为每个顶点在匹配中恰好有一条出边和一条入边）。
为什么这个算法是精确算法？
因为分数线性规划松弛的可行域与二分图指派问题的可行域相同，且后者整数性成立，所以线性规划的最优解就是整数解。因此，我们直接得到了原问题的最优解，而不是近似解。
但是，这个结论依赖于一个重要事实：原问题可以等价地转化为二分图最小权完美匹配问题。这正是因为环覆盖的约束（每个顶点出度=入度=1）恰好对应二分图中左部每个顶点匹配一条边到右部，右部每个顶点被匹配一次。所以，最小权环覆盖问题实际上就是最小权完美匹配问题在一般有向图上的表述。因此，该问题可以在多项式时间内精确求解，不需要近似算法。
等等，这似乎与之前说的问题NP难矛盾？实际上，最小环覆盖问题在一般有向图上是多项式时间可解的（因为它等价于指派问题），而旅行商问题是NP难的。两者的区别在于：旅行商问题要求一个单一哈密顿圈，而环覆盖允许多个不相交的环。因此，最小环覆盖问题确实是多项式时间可解的。
那么，为什么我们要讨论分数线性规划松弛和舍入呢？可能是因为在某些实际场景中，我们可能希望得到更快的近似算法，或者问题有额外的约束（例如每个环至少包含2个顶点，或者环的数量有限制），使得问题变成NP难。但在这里，我们只考虑基本的最小环覆盖问题，它是多项式时间可解的。
然而，为了符合题目要求（展示分数线性规划松弛与舍入算法），我们可以考虑一个变体问题：假设我们要求每个环至少包含 \(k\) 个顶点（\(k \geq 3\)），那么问题变成NP难。这时，我们可以使用分数线性规划松弛和舍入来设计近似算法。
四、变体问题：最小 \(k\)-环覆盖问题
假设我们要求每个环至少包含 \(k\) 个顶点（即不允许自环和2-环）。该问题是NP难的（当 \(k \geq 3\) 时）。我们设计一个基于线性规划松弛的近似算法。
4.1 整数规划模型
引入变量 \(x_e\) 和之前一样。约束包括：
- 出度=1，入度=1，\(x_e \in \{0,1\}\)。
- 消除小环约束：对于所有顶点子集 \(S \subset V\) 且 \(|S| < k\)，我们不能有选中的边全部在 \(S\) 内部形成环。形式化地，对于每个这样的 \(S\)，有：
\[ \sum_{e \in E(S)} x_e \leq |S| - 1 \]
其中 \(E(S)\) 是 \(S\) 内部的边集。这个约束确保任何选中的环至少包含 \(k\) 个顶点。
4.2 线性规划松弛
松弛掉整数约束，得到线性规划：
\[\begin{aligned} \min & \sum_{e \in E} w(e) x_e \\ \text{s.t.} & \sum_{v: (u, v) \in E} x_{(u, v)} = 1, \quad \forall u \in V \\ & \sum_{v: (v, u) \in E} x_{(v, u)} = 1, \quad \forall u \in V \\ & \sum_{e \in E(S)} x_e \leq |S| - 1, \quad \forall S \subset V, 1 \leq |S| < k \\ & 0 \leq x_e \leq 1, \quad \forall e \in E \end{aligned} \]
这个线性规划有指数多个约束（消除小环约束），但可以通过分离Oracle在多项式时间内求解（使用最小割来检测违反约束的集合 \(S\)）。
4.3 算法步骤
- 求解上述线性规划松弛，得到分数解 \(x^*\)。
- 对 \(x^*\) 进行随机化舍入：利用Birkhoff-von Neumann分解，将 \(x^*\) 表示为排列矩阵（环覆盖）的凸组合，然后随机选择一个排列。但是，由于消除小环约束是分数满足的，随机选择的排列可能违反小环约束（即可能产生小于 \(k\) 的环）。
- 处理小环：如果随机选择的排列中包含长度小于 \(k\) 的环，我们可以通过“合并”小环来修复。例如，可以将两个小环合并成一个较大的环，但需要额外增加一些边，从而增加权重。通过精心设计合并过程，可以证明最终得到的环覆盖的权重不超过 \(\alpha \cdot OPT_f\)，其中 \(\alpha\) 是某个常数（例如 \(\alpha = 2\) 或 \(\alpha = 3\)），从而得到一个常数近似算法。
由于该变体问题的算法较为复杂，且超出了基本线性规划舍入的范畴，这里不再展开细节。但核心思想是：线性规划松弛提供了一个下界，随机舍入给出一个初始解，再通过后处理（合并小环）得到可行解，并分析近似比。
五、总结
对于基本的最小环覆盖问题，我们可以通过转化为二分图最小权完美匹配问题，在多项式时间内精确求解。这实际上不需要复杂的舍入过程。
对于带最小环长约束的变体问题（NP难），我们可以使用分数线性规划松弛，并结合随机舍入与后处理，设计常数近似比的近似算法。
这个例子展示了线性规划松弛在组合优化问题中的强大作用：它不仅提供了问题最优值的下界，而且其分数解的结构可以启发舍入算法的设计，从而得到高质量的近似解。