基于线性规划的图最小边支配集问题的整数规划建模与舍入算法求解示例
1. 问题描述
我们考虑一个无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集合，\(E\) 是边集合。
一个边支配集 (Edge Dominating Set, EDS) 是指边集 \(D \subseteq E\)，满足图中的每一条边要么在 \(D\) 中，要么与 \(D\) 中的某条边相邻（即共享至少一个公共顶点）。
最小边支配集问题是寻找一个边数最少的边支配集。该问题是 NP-hard 的。
示例图：
设 \(G\) 有 5 个顶点和 6 条边：
- 顶点：\(V = \{1, 2, 3, 4, 5\}\)
- 边：\(E = \{a=(1,2), b=(2,3), c=(3,4), d=(4,5), e=(1,5), f=(2,4)\}\)
图示如下（用边标签表示）：
1 --a-- 2
| | \
e b f
| | \
5 --d-- 4 --c-- 3
目标：选择最少的边集合 \(D\)，使得每条边要么在 \(D\) 中，要么与 \(D\) 中至少一条边相邻。
2. 整数规划建模
2.1 决策变量
为每条边 \(e \in E\) 引入 0-1 变量：
\[x_e = \begin{cases} 1, & \text{如果边 } e \text{ 被选入支配集 } D \\ 0, & \text{否则} \end{cases} \]
2.2 目标函数
最小化所选边数：
\[\min \sum_{e \in E} x_e \]
2.3 支配约束
对每条边 \(e = (u, v) \in E\)，它必须被自身或相邻边支配。
一条边 \(e\) 的相邻边包括：
- 所有与顶点 \(u\) 关联的边（除了 \(e\) 自身）
- 所有与顶点 \(v\) 关联的边（除了 \(e\) 自身）
记 \(\delta(w)\) 表示与顶点 \(w\) 关联的边集。
则对边 \(e = (u, v)\)，其相邻边集合为：
\[N(e) = \big( \delta(u) \cup \delta(v) \big) \setminus \{e\} \]
约束条件为：
\[x_e + \sum_{f \in N(e)} x_f \ge 1, \quad \forall e \in E \]
即：对每条边 \(e\)，要么 \(e\) 被选（\(x_e = 1\)），要么至少有一条与 \(e\) 相邻的边被选。
2.4 整数规划模型
\[\begin{aligned} \min \quad & \sum_{e \in E} x_e \\ \text{s.t.} \quad & x_e + \sum_{f \in N(e)} x_f \ge 1, \quad \forall e \in E \\ & x_e \in \{0, 1\}, \quad \forall e \in E \end{aligned} \]
示例图的约束（用边标签 \(a,b,c,d,e,f\) 表示变量）：
- 对边 \(a=(1,2)\)：相邻边为 \(b, e, f\)（注意：\(a\) 自身也算）。
约束：\(x_a + x_b + x_e + x_f \ge 1\) - 对边 \(b=(2,3)\)：相邻边为 \(a, c, f\)（与顶点2相邻的 \(a, f\)；与顶点3相邻的 \(c\)）
约束：\(x_b + x_a + x_c + x_f \ge 1\) - 对边 \(c=(3,4)\)：相邻边为 \(b, d, f\)
约束：\(x_c + x_b + x_d + x_f \ge 1\) - 对边 \(d=(4,5)\)：相邻边为 \(c, e, f\)
约束：\(x_d + x_c + x_e + x_f \ge 1\) - 对边 \(e=(1,5)\)：相邻边为 \(a, d\)
约束：\(x_e + x_a + x_d \ge 1\) - 对边 \(f=(2,4)\)：相邻边为 \(a, b, c, d\)（与顶点2相邻的 \(a, b\)；与顶点4相邻的 \(c, d\)）
约束：\(x_f + x_a + x_b + x_c + x_d \ge 1\)
目标：\(\min \; x_a + x_b + x_c + x_d + x_e + x_f\)
3. 线性规划松弛与舍入算法
3.1 线性规划松弛
将整数约束 \(x_e \in \{0,1\}\) 松弛为：
\[0 \le x_e \le 1 \]
得到线性规划（LP）：
\[\begin{aligned} \min \quad & \sum_{e} x_e \\ \text{s.t.} \quad & x_e + \sum_{f \in N(e)} x_f \ge 1, \quad \forall e \in E \\ & 0 \le x_e \le 1 \end{aligned} \]
3.2 求解线性规划松弛
用单纯形法或内点法求解上述 LP。
对示例图，最优解为：
\[x_a = 0.5, \; x_b = 0, \; x_c = 0.5, \; x_d = 0, \; x_e = 0.5, \; x_f = 0 \]
目标值：\(0.5+0.5+0.5 = 1.5\)
验证约束：
- 边 \(a\)：\(0.5 + 0 + 0.5 + 0 = 1 \ge 1\) ✓
- 边 \(b\)：\(0 + 0.5 + 0.5 + 0 = 1\) ✓
- 边 \(c\)：\(0.5 + 0 + 0 + 0 = 0.5 < 1\)？不成立？仔细检查：
对 \(c=(3,4)\)，相邻边 \(N(c) = \{b, d, f\}\)，但 \(x_b=0, x_d=0, x_f=0\)，所以左边 = \(0.5 + 0 = 0.5\)，不满足约束。
发现错误：在输入约束时，对 \(c\) 的相邻边列表有误。
更正：边 \(c=(3,4)\)：
- 与顶点3相邻的边：\(b, c\)（排除自身 \(c\) 后剩下 \(b\)）
- 与顶点4相邻的边：\(d, f, c\)（排除自身 \(c\) 后剩下 \(d, f\)）
所以 \(N(c) = \{b, d, f\}\) 正确。
但 LP 解 \(x_c=0.5, x_b=0, x_d=0, x_f=0\) 给出左边 = 0.5，不满足约束 ≥1。
说明给出的 LP 解不是可行的。我们需要重新求解。
重新求解线性规划松弛（通过简单推理或求解器）：
观察对称性，可猜测一个对称解。尝试 \(x_a = x_c = x_e = 0.5\) 不满足 \(c\) 的约束，需要调整。
尝试等值解：设 \(x_e = t\) 对所有边 \(e\)。
约束变为：对任意边 \(e\)，有 \(t + (|N(e)|) t \ge 1\)。
图中最大度？实际上，每个约束的系数个数为 \(1 + |N(e)|\)，\(|N(e)|\) 是边 \(e\) 的相邻边数。
我们可以直接求解这个小型 LP。
手动枚举可行解：
一个简单可行解是 \(x_a = x_c = x_e = 0.5, x_b = x_d = x_f = 0\) 不满足 \(c\) 的约束。
尝试 \(x_a = x_c = 0.5, x_f = 0.5\)，其他为 0。
检查约束：
- \(a\)：0.5 + (0+0+0.5)=1 ✓
- \(b\)：0 + (0.5+0.5+0.5)=1.5 ✓
- \(c\)：0.5 + (0+0+0.5)=1 ✓
- \(d\)：0 + (0.5+0+0.5)=1 ✓
- \(e\)：0 + (0.5+0)=0.5 <1 不满足。
所以需调整。
找一个最小化和的可行解：注意到图中边数为 6，每个约束至少 1，可尝试所有变量 = 1/3。
计算每个约束左边：
- \(a\)：1/3 + (1/3+1/3+1/3)=4/3>1 ✓
- \(b\)：1/3 + (1/3+1/3+1/3)=4/3 ✓
- \(c\)：1/3 + (1/3+1/3+1/3)=4/3 ✓
- \(d\)：1/3 + (1/3+1/3+1/3)=4/3 ✓
- \(e\)：1/3 + (1/3+1/3)=1 ✓
- \(f\)：1/3 + (1/3+1/3+1/3+1/3)=5/3 ✓
可行。目标值 = 6*(1/3) = 2。
但可能存在更小的和。
实际上，从图结构看，最优 LP 值可能是 2。我们接受这个可行解：
\(x_a = x_b = x_c = x_d = x_e = x_f = 1/3\)，目标值 = 2。
3.3 舍入算法（随机舍入）
一个简单的舍入策略：
给定 LP 最优解 \(x^*\)，以概率 \(x_e^*\) 独立地将每条边 \(e\) 选入 \(D\)。
但这样可能不满足所有支配约束，因为一条边 \(e\) 可能自身未被选，且相邻边也未被选。
改进的舍入方法：两阶段舍入（基于线性规划舍入的近似算法常见技巧）
步骤：
- 求解 LP 松弛，得到最优解 \(x^*\)。
- 独立地以概率 \(\min(1, \alpha x_e^*)\) 将边 \(e\) 选入集合 \(D'\)，其中 \(\alpha \ge 1\) 是放大因子（常取 \(\alpha = 2\)）。
- 在 \(D'\) 的基础上，检查哪些边未被支配：对每条边 \(e \notin D'\)，若 \(e\) 的相邻边中无 \(D'\) 的边，则将 \(e\) 的任意一条相邻边加入 \(D'\)（或直接将 \(e\) 加入 \(D'\)），得到最终边支配集 \(D\)。
近似比：可以证明该算法得到解的期望大小不超过 \(2 \cdot \text{OPT}_{LP} \le 2 \cdot \text{OPT}_{整数}\)，即 2-近似算法。
3.4 在示例图上执行舍入算法
假设 LP 最优解为 \(x_e^* = 1/3\) 对所有 \(e\)（目标值 2）。
取 \(\alpha = 2\)，则概率 \(p_e = \min(1, 2 \cdot 1/3) = 2/3\)。
随机试验模拟（一次随机结果）：
生成随机数决定每条边是否选入 \(D'\)（概率 2/3）：
- 设结果：\(a=1, b=0, c=1, d=0, e=0, f=1\)（1 表示选中）
\(D' = \{a, c, f\}\)
检查未被支配的边：
- 边 \(a \in D'\) ✓
- 边 \(b \notin D'\)，相邻边有 \(a, c, f \in D'\) ✓
- 边 \(c \in D'\) ✓
- 边 \(d \notin D'\)，相邻边有 \(c, e, f\)，其中 \(c, f \in D'\) ✓
- 边 \(e \notin D'\)，相邻边有 \(a, d\)，其中 \(a \in D'\) ✓
- 边 \(f \in D'\) ✓
所有边均被支配，因此 \(D = D' = \{a, c, f\}\)，大小为 3。
整数最优解（可验证）可能是 2（例如选边 \(a\) 和 \(d\) 不一定支配所有边？验证：选 \(\{a, d\}\)，边 \(f\) 与 \(a\) 相邻 ✓，边 \(c\) 与 \(d\) 相邻 ✓，边 \(b\) 与 \(a\) 相邻 ✓，边 \(e\) 与 \(a,d\) 相邻 ✓，边 \(a,d\) 自身 ✓。确实可行）。
所以整数最优解 OPT = 2，我们得到 3，近似比 1.5。
4. 总结
- 建模：将最小边支配集问题转化为 0-1 整数规划，约束保证每条边被自身或相邻边覆盖。
- 松弛：将整数变量松弛为连续变量，得到线性规划，可高效求解。
- 舍入：通过概率舍入与后处理，得到整数可行解，并证明其近似比。
- 应用：该问题在网络设计、传感器覆盖中有应用，如选择最少的链路监控整个网络。
此方法展示了如何用线性规划松弛+舍入解决 NP-hard 组合优化问题，平衡求解效率与解的质量。