基于线性规划的图最小顶点覆盖问题的整数规划建模与松弛舍入算法求解示例
我将为您讲解如何使用整数规划建模图最小顶点覆盖问题，并通过线性规划松弛与舍入算法进行近似求解。这个过程将展示如何将组合优化问题转化为数学规划模型，并利用线性规划工具获得高质量的近似解。
问题描述
图最小顶点覆盖问题：给定一个无向图G=(V,E)，其中V是顶点集合，E是边集合。一个顶点覆盖是指一个顶点子集S⊆V，使得图中的每条边至少有一个端点属于S。最小顶点覆盖问题是寻找一个顶点数最少的顶点覆盖。
这是一个经典的NP难问题，在实际应用中广泛存在，如网络监控、电路设计等领域。
解题过程
步骤1：整数规划建模
首先，我们为每个顶点引入一个二进制决策变量：
- \(x_v = 1\) 如果顶点v被选入顶点覆盖S
- \(x_v = 0\) 如果顶点v未被选入S
目标是最小化被选顶点的总数，同时满足每条边至少有一个端点被覆盖的约束。
整数规划模型：
\[\text{最小化} \sum_{v \in V} x_v \]
\[ \text{满足} \quad x_u + x_v \geq 1 \quad \forall (u,v) \in E \]
\[ x_v \in \{0,1\} \quad \forall v \in V \]
每条边约束\(x_u + x_v \geq 1\)确保边(u,v)的两个端点至少有一个被选中。
步骤2：线性规划松弛
由于整数规划是NP难的，我们将其松弛为线性规划问题，将整数约束放宽为连续约束：
线性规划松弛模型：
\[\text{最小化} \sum_{v \in V} x_v \]
\[ \text{满足} \quad x_u + x_v \geq 1 \quad \forall (u,v) \in E \]
\[ 0 \leq x_v \leq 1 \quad \forall v \in V \]
这个线性规划问题可以在多项式时间内求解，得到最优解\(x^*\)。
步骤3：舍入策略
线性规划的解\(x^*\)是0到1之间的分数值，我们需要将其舍入为整数解（0或1）。采用简单的随机舍入策略：
对于每个顶点v∈V：
- 以概率\(x_v^*\)将\(x_v\)设为1（选入覆盖）
- 以概率\(1-x_v^*\)将\(x_v\)设为0（不选入覆盖）
定理：这个舍入策略得到的解是一个顶点覆盖，且期望顶点数为线性规划最优值的2倍以内。
证明：
- 覆盖性：对于任意边(u,v)，约束\(x_u^* + x_v^* \geq 1\)确保至少有一个端点的值≥0.5。舍入后边被覆盖的概率为：
\[ 1 - (1-x_u^*)(1-x_v^*) = x_u^* + x_v^* - x_u^*x_v^* \geq 1 - (1-x_u^*)(1-x_v^*) \]
实际上，由于\(x_u^* + x_v^* \geq 1\)，边未被覆盖的概率\((1-x_u^*)(1-x_v^*)\)很小。
- 近似比：期望顶点数为\(\sum_{v \in V} x_v^*\)，即线性规划最优值。但确定性舍入（如设\(x_v=1\)当\(x_v^* \geq 0.5\)）可保证2-近似比。
步骤4：确定性舍入算法
更实用的确定性舍入算法：
- 求解线性规划松弛，得到分数解\(x^*\)
- 构造顶点覆盖S：\(S = \{v \in V : x_v^* \geq 0.5\}\)
合理性分析：
- 对于任意边(u,v)，由于\(x_u^* + x_v^* \geq 1\)，不可能同时有\(x_u^* < 0.5\)和\(x_v^* < 0.5\)
- 因此至少有一个端点满足\(x^* \geq 0.5\)，会被加入S
- 每个顶点在S中的"代价"最多是分数解的2倍（因为\(x_v^* \geq 0.5\)时，舍入后为1 ≤ 2×0.5 ≤ 2x_v^*）
步骤5：实例演示
考虑一个简单图：三角形图（3个顶点，3条边）
- 顶点：A,B,C
- 边：(A,B), (B,C), (A,C)
整数规划模型：
最小化 \(x_A + x_B + x_C\)
满足：
\(x_A + x_B \geq 1\)
\(x_B + x_C \geq 1\)
\(x_A + x_C \geq 1\)
\(x_A, x_B, x_C \in \{0,1\}\)
线性规划松弛：允许\(0 \leq x_v \leq 1\)
求解松弛：最优解为\(x_A^* = x_B^* = x_C^* = 0.5\)，目标值1.5
舍入：由于所有\(x_v^* = 0.5\)，舍入后得到S={A,B,C}，大小为3
实际上，最小顶点覆盖大小为2（任意两个顶点即可覆盖所有边），但线性规划舍入给出了一个2-近似解（3/2=1.5倍，小于2倍）。
算法总结
这个基于线性规划松弛与舍入的算法：
- 将整数规划松弛为线性规划
- 求解线性规划得到分数解
- 通过阈值舍入（如≥0.5）获得整数解
- 保证解是可行的顶点覆盖
- 具有2-近似比保证
该方法展示了如何利用线性规划工具解决组合优化问题，平衡计算效率与解的质量。