基于线性规划的图最小顶点覆盖问题的分支定界算法求解示例
我将为你讲解如何用分支定界算法求解最小顶点覆盖问题。这是一个经典的组合优化问题，我们首先建立线性规划模型，然后通过分支定界找到整数最优解。
问题描述
最小顶点覆盖问题：给定一个无向图G = (V, E)，其中V是顶点集合，E是边集合。一个顶点覆盖是一个顶点子集S ⊆ V，使得图中的每一条边至少有一个端点在S中。我们的目标是找到包含顶点数最少的顶点覆盖。
这是一个NP-hard问题。我们通过以下步骤求解：
- 建立整数规划模型
- 求解线性规划松弛
- 基于松弛解进行分支定界搜索
- 得到最优整数解
1. 建立整数规划模型
决策变量：
对于每个顶点i ∈ V，定义二元变量：
- \(x_i = 1\) 表示顶点i被选入覆盖集
- \(x_i = 0\) 表示顶点i未被选中
目标函数：最小化覆盖中的顶点数
\[\min \sum_{i \in V} x_i \]
约束条件：每条边至少有一个端点被覆盖
对于每条边(i, j) ∈ E：
\[x_i + x_j \geq 1 \]
整数约束：
\[x_i \in \{0, 1\}, \quad \forall i \in V \]
这是0-1整数规划问题。如果我们放松整数约束，允许 \(0 \leq x_i \leq 1\)，就得到了线性规划松弛。
2. 构建示例图
为了具体说明，考虑一个简单但非平凡的例子：
- 顶点：V = {1, 2, 3, 4, 5}
- 边：E = {(1,2), (1,3), (2,3), (2,4), (3,4), (4,5)}
这是一个包含5个顶点、6条边的图。显然，最小顶点覆盖的大小应该是3（比如选择顶点{2,3,4}或{1,4,5}等）。
3. 求解线性规划松弛
首先求解松弛问题（去掉整数约束）：
松弛问题：
\[\min x_1 + x_2 + x_3 + x_4 + x_5 \]
约束：
\[\begin{aligned} &x_1 + x_2 \geq 1 \quad \text{(边1-2)} \\ &x_1 + x_3 \geq 1 \quad \text{(边1-3)} \\ &x_2 + x_3 \geq 1 \quad \text{(边2-3)} \\ &x_2 + x_4 \geq 1 \quad \text{(边2-4)} \\ &x_3 + x_4 \geq 1 \quad \text{(边3-4)} \\ &x_4 + x_5 \geq 1 \quad \text{(边4-5)} \\ &0 \leq x_i \leq 1, \quad i=1,...,5 \end{aligned} \]
求解松弛：
这是一个线性规划，可以用单纯形法求解。我们观察结构：
- 边(1,2,3)形成一个三角形，覆盖三角形需要至少2个顶点（因为每个边都要覆盖）
- 顶点4与2、3、5相连
- 顶点5只与4相连
手工求解思路：
由于对称性，尝试对称解。实际上，最优松弛解可以通过互补松弛条件或简单推理得到：
设 \(x_1 = 0.5, x_2 = 0.5, x_3 = 0.5\) 可以覆盖三角形的三条边（每条边的和=1）
但这样 \(x_2+x_4 \geq 1\) ⇒ 0.5 + \(x_4\) ≥ 1 ⇒ \(x_4\) ≥ 0.5
同样 \(x_3+x_4 \geq 1\) ⇒ 同样要求 \(x_4\) ≥ 0.5
然后 \(x_4+x_5 \geq 1\) ⇒ 0.5 + \(x_5\) ≥ 1 ⇒ \(x_5\) ≥ 0.5
目标值 = 0.5+0.5+0.5+0.5+0.5 = 2.5
检查是否可更小？如果让某个变量=1，可能增加总值。例如，如果设 \(x_1=0, x_2=1, x_3=1\)，则三角形覆盖，但值=2。然后 \(x_2+x_4 \geq 1\) ⇒ 1+ \(x_4\) ≥ 1 ⇒ \(x_4\) ≥ 0，但 \(x_3+x_4 \geq 1\) ⇒ 1+ \(x_4\) ≥ 1 ⇒ 自动满足。然而 \(x_4+x_5 \geq 1\) ⇒ 如果 \(x_4=0\)，则需要 \(x_5=1\)，总值=0+1+1+0+1=3，比2.5大。
实际上，最优松弛解是 \(x_1 = 0.5, x_2 = 0.5, x_3 = 0.5, x_4 = 0.5, x_5 = 0.5\)，目标值=2.5。可以验证所有约束都满足（每条边的和=1）。
松弛下界：2.5
整数最优解的上界：我们可以找到一个可行整数解，比如选择{1,2,3,4}，大小=4。但更好的是{2,3,4}，大小=3。所以初始上界UB=3。
由于2.5 < 3，我们需要分支定界。
4. 分支定界过程
分支定界树搜索过程：
节点0：松弛解 \(x=(0.5,0.5,0.5,0.5,0.5)\)，目标值=2.5
- 下界LB=2.5
- 当前最好整数解：{2,3,4}，大小=3，UB=3
由于松弛解不是全整数，需要分支。选择分支变量：通常选分数值最接近0.5的变量。这里所有都是0.5，可以选\(x_1\)。
分支1：固定 \(x_1 = 0\)
子问题变为：
\[\min x_2 + x_3 + x_4 + x_5 \]
约束：
\[\begin{aligned} &x_2 \geq 1 \quad \text{(由}x_1+x_2 \geq 1\text{)} \\ &x_3 \geq 1 \quad \text{(由}x_1+x_3 \geq 1\text{)} \\ &x_2 + x_3 \geq 1 \quad \text{(自动满足，因为}x_2\geq1\text{)} \\ &x_2 + x_4 \geq 1 \quad \text{(自动满足)} \\ &x_3 + x_4 \geq 1 \quad \text{(自动满足)} \\ &x_4 + x_5 \geq 1 \\ &0 \leq x_i \leq 1 \end{aligned} \]
由前两个约束，\(x_2 \geq 1, x_3 \geq 1\)，但上限为1，所以 \(x_2=1, x_3=1\)。
然后 \(x_4+x_5 \geq 1\)。最小化目标：\(1+1+x_4+x_5 = 2+x_4+x_5\)，在 \(x_4+x_5 \geq 1\) 下，最小为3，当 \(x_4=1, x_5=0\) 或 \(x_4=0, x_5=1\) 或分数组合。
松弛解：\(x_1=0, x_2=1, x_3=1, x_4=0.5, x_5=0.5\)，目标值=3.0
这是整数可行吗？不完全是，但目标值=3.0正好等于当前上界3。任何整数解不会比3更好，所以这个分支的下界=3。
由于下界=3=UB，这个分支不会产生更好的解，剪枝（bound剪枝）。
分支2：固定 \(x_1 = 1\)
子问题：
\[\min 1 + x_2 + x_3 + x_4 + x_5 \]
约束：
\[\begin{aligned} &1 + x_2 \geq 1 \quad \Rightarrow \quad x_2 \geq 0 \text{(无约束)} \\ &1 + x_3 \geq 1 \quad \Rightarrow \quad x_3 \geq 0 \\ &x_2 + x_3 \geq 1 \\ &x_2 + x_4 \geq 1 \\ &x_3 + x_4 \geq 1 \\ &x_4 + x_5 \geq 1 \\ &0 \leq x_i \leq 1 \end{aligned} \]
目标变为常数1 + 最小化 \(x_2+x_3+x_4+x_5\)。
观察：由于 \(x_1=1\) 已经覆盖了边(1,2)和(1,3)，所以约束 \(x_1+x_2 \geq 1\) 和 \(x_1+x_3 \geq 1\) 变为冗余。但约束 \(x_2+x_3 \geq 1\) 仍然需要，因为边(2,3)未被覆盖。
试着最小化：我们需要覆盖三角形{2,3,4}的边。实际上，子图{2,3,4}构成一个三角形加上边(4,5)。
尝试：设 \(x_2=0.5, x_3=0.5, x_4=0.5, x_5=0.5\)，检查约束：
- \(x_2+x_3=1\) ≥1 ✓
- \(x_2+x_4=1\) ≥1 ✓
- \(x_3+x_4=1\) ≥1 ✓
- \(x_4+x_5=1\) ≥1 ✓
目标值=1+0.5+0.5+0.5+0.5=3.0
是否可以更小？如果让某个变量=0，可能会迫使其他变量增大。例如，设 \(x_2=0\)，则 \(x_2+x_3 \geq 1\) ⇒ \(x_3 \geq 1\)，所以 \(x_3=1\)。
然后 \(x_3+x_4 \geq 1\) ⇒ 1+ \(x_4\) ≥1 ⇒ 自动满足，但 \(x_2+x_4 \geq 1\) ⇒ 0+ \(x_4\) ≥1 ⇒ \(x_4=1\)。
然后 \(x_4+x_5 \geq 1\) ⇒ 1+ \(x_5\) ≥1 ⇒ 自动满足，最小化让 \(x_5=0\)。
目标值=1+0+1+1+0=3.0，相同。
另一个对称情况：\(x_2=1, x_3=0\) 同理。
所以最小松弛值=3.0。下界=3.0。
由于下界=3=UB，这个分支也剪枝。
5. 结论
所有分支都被剪枝，当前最好整数解{2,3,4}（大小为3）即为最优解。
验证：检查{2,3,4}是否覆盖所有边：
- 边(1,2)：顶点2覆盖 ✓
- 边(1,3)：顶点3覆盖 ✓
- 边(2,3)：顶点2或3覆盖 ✓
- 边(2,4)：顶点2或4覆盖 ✓
- 边(3,4)：顶点3或4覆盖 ✓
- 边(4,5)：顶点4覆盖 ✓
所有边被覆盖。
最小顶点覆盖大小：3
6. 算法总结
- 建模：将最小顶点覆盖表示为0-1整数规划
- 线性规划松弛：去掉整数约束，得到下界
- 分支：选择分数变量，创建两个子问题（固定为0或1）
- 定界：
- 如果松弛值 ≥ 当前最好整数解值，剪枝
- 如果松弛解是整数且值 < 当前最好解，更新最好解
- 搜索：深度优先或最佳下界优先搜索分支树
- 终止：当所有节点处理完毕，得到最优解
关键点：
- 线性规划松弛提供了最优值的下界
- 分支定界系统地搜索解空间
- 剪枝减少搜索量
- 对于最小顶点覆盖，线性规划松弛总是给出下界，但可能需要很多分支才能找到整数最优解
这个示例展示了如何将组合优化问题转化为整数规划，并通过分支定界算法求解。