基于线性规划的图最小顶点覆盖问题的拉格朗日松弛与次梯度优化求解示例
1. 问题描述
图的最小顶点覆盖问题 是图论和组合优化中的一个经典NP难问题。给定一个无向图 G=(V,E)，其中 V 是顶点集，E 是边集。一个顶点覆盖是指一个顶点子集 C ⊆ V，使得图中的每条边至少有一个端点属于 C。最小顶点覆盖问题的目标是找到这样一个顶点子集 C，使得其包含的顶点数量 |C| 最少。
尽管最小顶点覆盖问题是NP难的，但它有一个重要的性质：它是一个可以近似到2倍的整数规划问题，并且可以通过线性规划松弛和舍入等技术来解决。本示例中，我们将不直接求解其整数规划模型，而是先构造其整数规划模型，然后通过拉格朗日松弛方法松弛掉一个约束集，将原问题分解为较易求解的子问题，再结合次梯度优化算法来迭代更新拉格朗日乘子，逐步逼近最优解（或最优下界）。最后，我们会利用求得的下界和启发式方法构造一个可行的顶点覆盖，从而获得一个近似解。
2. 整数规划建模
首先，为每个顶点 i ∈ V 定义一个二元决策变量 \(x_i\)：
- 若顶点 i 被选入覆盖集 C，则 \(x_i = 1\)；
- 否则 \(x_i = 0\)。
最小顶点覆盖问题的整数规划模型为：
\[\begin{aligned} \min \quad & \sum_{i \in V} x_i \\ \text{s.t.} \quad & x_i + x_j \geq 1, \quad \forall (i,j) \in E, \\ & x_i \in \{0,1\}, \quad \forall i \in V. \end{aligned} \]
其中，目标函数最小化所选顶点总数；约束条件确保每条边 (i,j) 至少有一个端点被覆盖（即 \(x_i = 1\) 或 \(x_j = 1\)）；变量是二元的。
这是一个0-1整数规划问题。当图规模较大时，直接求解可能非常耗时。我们可以通过拉格朗日松弛来获得一个易于求解的下界，并指导寻找可行解。
3. 拉格朗日松弛
在拉格朗日松弛中，我们选择一个“复杂”的约束集，将其移到目标函数中，并为每个这样的约束引入一个非负的拉格朗日乘子，从而将原问题分解为更简单的子问题。这里，我们选择松弛覆盖约束 \(x_i + x_j \geq 1\)。对于每条边 e = (i,j) ∈ E，引入非负拉格朗日乘子 λ_e ≥ 0。
构造拉格朗日函数：
\[L(x, \lambda) = \sum_{i \in V} x_i + \sum_{e=(i,j) \in E} \lambda_e (1 - x_i - x_j). \]
这里，我们将约束改写为 \(1 - x_i - x_j \leq 0\)，并加到目标函数中（带有乘子 λ_e）。
对于给定的 λ ≥ 0，拉格朗日对偶函数是：
\[\theta(\lambda) = \min_{x \in \{0,1\}^{|V|}} L(x, \lambda). \]
注意，我们只要求 x 是二元变量，而不再需要满足覆盖约束。这样，原问题被分解为关于每个顶点 i 独立的子问题。
将 L(x, λ) 重新整理：
\[L(x, \lambda) = \sum_{i \in V} x_i - \sum_{e=(i,j) \in E} \lambda_e (x_i + x_j) + \sum_{e \in E} \lambda_e. \]
对于每个顶点 i，我们收集所有与 i 关联的边上的乘子。设 δ(i) 表示与顶点 i 相关联的边集，则包含 \(x_i\) 的项为：
\[x_i \cdot \left( 1 - \sum_{e \in \delta(i)} \lambda_e \right). \]
注意，每条边 e=(i,j) 的 λ_e 会在顶点 i 和 j 上各减一次。
因此，
\[L(x, \lambda) = \sum_{i \in V} \left[ x_i \cdot \left( 1 - \sum_{e \in \delta(i)} \lambda_e \right) \right] + \sum_{e \in E} \lambda_e. \]
由于 \(x_i \in \{0,1\}\)，并且目标是最小化，对于给定的 λ，每个子问题的最优解为：
- 如果系数 \(1 - \sum_{e \in \delta(i)} \lambda_e < 0\)，则令 \(x_i = 1\) 会使该项为负，有助于减小目标值；
- 如果系数 \(1 - \sum_{e \in \delta(i)} \lambda_e > 0\)，则令 \(x_i = 0\) 更优（因为 \(x_i = 1\) 会带来正贡献）；
- 如果系数等于0，则 \(x_i\) 取0或1对目标值无影响，但通常可以取0。
因此，拉格朗日对偶函数的最优解为：
\[x_i^*(\lambda) = \begin{cases} 1, & \text{if } 1 - \sum_{e \in \delta(i)} \lambda_e < 0,\\ 0, & \text{otherwise}. \end{cases} \]
为了方便，我们通常约定：当系数为负时取1，否则取0。
代入得到：
\[\theta(\lambda) = \sum_{i \in V} \min\left(0, \; 1 - \sum_{e \in \delta(i)} \lambda_e \right) + \sum_{e \in E} \lambda_e. \]
（注意：当 \(1 - \sum_{e \in \delta(i)} \lambda_e < 0\) 时，该项就是 \(1 - \sum_{e \in \delta(i)} \lambda_e\)；当 ≥0 时，该项为0，符合 \(x_i=0\) 的情况。）
由于 \(\theta(\lambda)\) 是凹函数（对偶函数总是凹的），我们想要最大化 \(\theta(\lambda)\) 来获得最紧的下界，这就是拉格朗日对偶问题：
\[\max_{\lambda \geq 0} \theta(\lambda). \]
4. 次梯度优化
为了求解对偶问题 \(\max_{\lambda \geq 0} \theta(\lambda)\)，我们使用次梯度优化（Subgradient Optimization）算法。这是因为 \(\theta(\lambda)\) 虽然凹，但不一定处处可导（由于 min 函数的存在），但其在任意点 λ 处都有一个次梯度。
对于给定的 λ，我们计算一个次梯度 g(λ)，其分量 \(g_e(\lambda)\) 对应于每条边 e=(i,j)：
\[g_e(\lambda) = 1 - x_i^*(\lambda) - x_j^*(\lambda), \]
其中 \(x^*(\lambda)\) 是上述对偶函数的最优解。这个次梯度实际上是松弛约束 \(1 - x_i - x_j \leq 0\) 在最优解处的违反程度：如果约束被满足（即 \(x_i + x_j \geq 1\)），则 \(1 - x_i - x_j \leq 0\)，次梯度非正；如果违反，则次梯度为正。
次梯度优化迭代步骤：
- 初始化：设置乘子向量 \(\lambda^0 = 0\)（或随机小的正数），设置最大迭代次数 T，步长序列 \(t_k\)（如 \(t_k = \alpha / k\) 或恒定步长）。
- 对于 k = 0,1,...,T-1：
a. 计算当前解 \(x^k = x^*(\lambda^k)\) 和当前对偶值 \(\theta(\lambda^k)\)。
b. 计算次梯度 \(g^k\)，其中 \(g_e^k = 1 - x_i^k - x_j^k\)。
c. 更新乘子： \(\lambda^{k+1} = \max(0, \; \lambda^k + t_k \cdot g^k)\)。
d. 可选：记录历史最佳对偶值 \(\theta_{\text{best}} = \max(\theta_{\text{best}}, \theta(\lambda^k))\)。 - 输出最终乘子 λ^T 及对应的对偶值。
注意：由于对偶函数是凹的，次梯度上升是可行的。但次梯度法不保证对偶值单调上升，因此需要保留历史最佳值。
5. 构造可行解（顶点覆盖）
在次梯度优化结束后，我们得到一个接近最优的乘子 λ* 及其对应的 0-1 向量 \(x^*\)。然而，由于我们松弛了覆盖约束，\(x^*\) 可能不满足所有覆盖约束（即可能存在边 (i,j) 使得 \(x_i^* = x_j^* = 0\)）。为了得到一个可行顶点覆盖，我们需要对 \(x^*\) 进行修正。
一个简单有效的启发式是：对每条未被覆盖的边，将其任意一个端点加入覆盖集。更系统的方法是：
- 初始化可行覆盖集 C = ∅。
- 对于所有满足 \(x_i^* = 1\) 的顶点 i，直接加入 C。
- 检查所有边 e=(i,j)：
- 如果 i ∈ C 或 j ∈ C，则该边已被覆盖。
- 否则（即 i 和 j 都不在 C 中），将 i 或 j 中度数较大的一个加入 C（这样可以覆盖更多未覆盖边）。
- 最终得到的 C 是一个可行顶点覆盖。
我们可以比较这个覆盖的大小与对偶下界，从而评估解的质量。
6. 实例演示
考虑一个简单无向图：顶点集 V={1,2,3,4}，边集 E={(1,2), (2,3), (3,4), (4,1), (1,3)}（即一个四边形加一条对角线）。我们演示拉格朗日松弛与次梯度优化。
步骤1：建立模型
决策变量：\(x_1, x_2, x_3, x_4 \in \{0,1\}\)。
目标：最小化 \(x_1+x_2+x_3+x_4\)。
约束：
- 边(1,2): \(x_1+x_2 \ge 1\)。
- 边(2,3): \(x_2+x_3 \ge 1\)。
- 边(3,4): \(x_3+x_4 \ge 1\)。
- 边(4,1): \(x_4+x_1 \ge 1\)。
- 边(1,3): \(x_1+x_3 \ge 1\)。
显然，一个最小顶点覆盖是 {1,3} 或 {2,4}，大小均为2。
步骤2：拉格朗日松弛
引入乘子 λ_12, λ_23, λ_34, λ_41, λ_13 ≥ 0。
拉格朗日函数：
\[L = x_1+x_2+x_3+x_4 + \lambda_{12}(1-x_1-x_2) + \lambda_{23}(1-x_2-x_3) + \lambda_{34}(1-x_3-x_4) + \lambda_{41}(1-x_4-x_1) + \lambda_{13}(1-x_1-x_3). \]
整理每个顶点系数：
- 对于 x_1: 1 - λ_12 - λ_41 - λ_13。
- 对于 x_2: 1 - λ_12 - λ_23。
- 对于 x_3: 1 - λ_23 - λ_34 - λ_13。
- 对于 x_4: 1 - λ_34 - λ_41。
常数项： λ_12+λ_23+λ_34+λ_41+λ_13。
步骤3：次梯度优化迭代
我们手动模拟几步，以理解过程。初始化 λ=0。
- 系数：x_1:1, x_2:1, x_3:1, x_4:1 全部为正 ⇒ 最优解 \(x^* = (0,0,0,0)\)。
- 对偶值 θ(0) = 0 + 0 = 0。
- 次梯度 g: 对每条边，g_e = 1-0-0=1，所以 g=(1,1,1,1,1)。
- 更新：取步长 t=0.5，λ^1 = 0 + 0.5*1 = 0.5 对所有边。
下一轮：
- 系数：x_1: 1-0.5-0.5-0.5 = -0.5 ⇒ 取1；x_2: 1-0.5-0.5=0 ⇒ 取0；x_3: 1-0.5-0.5-0.5=-0.5 ⇒ 取1；x_4: 1-0.5-0.5=0 ⇒ 取0。所以 \(x^*=(1,0,1,0)\)。
- 对偶值：θ = ( -0.5 + 0 + -0.5 + 0 ) + (0.5*5) = -1 + 2.5 = 1.5。
- 检查覆盖：边(1,2):1+0=1 ✔；(2,3):0+1=1 ✔；(3,4):1+0=1 ✔；(4,1):0+1=1 ✔；(1,3):1+1=2 ✔。所有边已被覆盖！此时 \(x^*\) 恰好是可行解（覆盖集 {1,3}），且目标值为2，而对偶值1.5是下界。
继续迭代可以改进对偶值，但这里已经得到可行解。
步骤4：构造可行解
此例中，\(x^*\) 已经是可行顶点覆盖 {1,3}，大小为2，等于最优解。
7. 总结
通过这个示例，我们展示了如何利用拉格朗日松弛将最小顶点覆盖的整数规划问题松弛为一个易于求解的0-1无约束问题，然后通过次梯度优化来最大化对偶函数，获得原问题最优值的一个下界。同时，利用松弛解构造可行顶点覆盖。这个方法不仅可以用于获得近似解，还可以在分支定界法中提供下界，加速精确算法的求解。尽管本示例是教学性的，但其思想可推广到更大规模的问题和其他类似整数规划问题中。