基于线性规划的图最小权支配集问题的半定规划松弛求解示例
我将为您讲解如何利用半定规划（SDP）松弛来近似求解图的最小权支配集（Minimum Weight Dominating Set, MWDS）问题。这是一个NP难问题，我们可以通过建立其整数规划模型，再将其松弛为半定规划，最后设计舍入算法来获得近似解。
1. 问题描述
我们有一个无向图 \(G = (V, E)\)，其中 \(V = \{1, 2, \dots, n\}\) 是顶点集合，\(E\) 是边集合。每个顶点 \(i \in V\) 有一个非负权重 \(w_i \geq 0\)。一个顶点集合 \(S \subseteq V\) 称为一个支配集（Dominating Set），如果对于图中任意一个顶点 \(v \in V\)，要么 \(v \in S\)，要么 \(v\) 至少与 \(S\) 中的一个顶点相邻。
最小权支配集问题的目标是找到一个支配集 \(S\)，使得其总权重 \(\sum_{i \in S} w_i\) 最小。
2. 整数规划建模
我们为每个顶点 \(i\) 引入一个0-1决策变量 \(x_i\)：
- \(x_i = 1\) 表示顶点 \(i\) 被选入支配集 \(S\)；
- \(x_i = 0\) 表示未被选入。
那么，支配集的条件可以表述为：对于每个顶点 \(i\)，要么 \(x_i = 1\)，要么对于其某个邻居 \(j\)（即存在边 \((i, j) \in E\)），有 \(x_j = 1\)。这可以写成线性约束：
\[x_i + \sum_{j: (i, j) \in E} x_j \geq 1 \quad \forall i \in V \]
目标是最小化总权重：
\[\min \sum_{i=1}^n w_i x_i \]
再加上整数约束：
\[x_i \in \{0, 1\}, \quad \forall i \in V \]
这就是一个整数线性规划（ILP）模型。
3. 半定规划（SDP）松弛的构建
由于0-1整数规划是NP难的，我们需要松弛。半定规划松弛是一种比线性规划松弛更强的松弛方式，常用于获得更好的近似比。
3.1 将0-1变量转化为向量形式
我们引入 \(n\) 个单位向量 \(\mathbf{v}_i \in \mathbb{R}^{n+1}\)（维度多一维是为了便于处理），并令：
- 选一个额外的参考向量 \(\mathbf{v}_0 \in \mathbb{R}^{n+1}\)，其长度固定。
- 我们希望：当 \(x_i = 1\) 时，\(\mathbf{v}_i\) 与 \(\mathbf{v}_0\) 同方向（点积为1）；当 \(x_i = 0\) 时，\(\mathbf{v}_i\) 与 \(\mathbf{v}_0\) 垂直（点积为0）。
这可以通过约束 \(\mathbf{v}_i \cdot \mathbf{v}_0 = x_i\) 来实现，但直接这样是线性的。更常用的技巧是利用Gram矩阵。
3.2 构建半定规划松弛的标准方法
定义对称矩阵 \(Y \in \mathbb{R}^{(n+1) \times (n+1)}\)，其中 \(Y_{ij} = \mathbf{v}_i \cdot \mathbf{v}_j\)。对于我们的向量集 \(\{\mathbf{v}_0, \mathbf{v}_1, \dots, \mathbf{v}_n\}\)，Gram矩阵 \(Y\) 是半正定的（记为 \(Y \succeq 0\)），且对角线元素 \(Y_{ii} = \|\mathbf{v}_i\|^2\)。
我们固定 \(\mathbf{v}_0\) 为单位向量，即 \(Y_{00} = 1\)。我们令：
- \(Y_{0i} = \mathbf{v}_0 \cdot \mathbf{v}_i\) 对应于原始变量 \(x_i\)。
- 对每个顶点 \(i\)，支配约束 \(x_i + \sum_{j \in N(i)} x_j \geq 1\) 可以写成：
\[Y_{0i} + \sum_{j \in N(i)} Y_{0j} \geq 1 \]
这里 \(N(i)\) 表示顶点 \(i\) 的邻居集合（不包括自己）。
但为了加强松弛，我们可以引入所有向量之间的内积约束。由于 \(x_i\) 是0-1变量，我们希望 \(x_i^2 = x_i\)，这对应于：
\[Y_{0i} = Y_{ii} \]
因为 \(Y_{0i} = \mathbf{v}_0 \cdot \mathbf{v}_i\)，而 \(Y_{ii} = \|\mathbf{v}_i\|^2\)。如果 \(\mathbf{v}_i\) 是单位向量，则 \(Y_{ii} = 1\)。但我们可以放松为：
\[Y_{ii} = Y_{0i} \]
以及 \(Y_{0i} \geq 0\) 和 \(Y_{ii} \leq 1\)（因为 \(\|\mathbf{v}_i\|^2 \leq 1\) 可以加入）。
最终，我们得到半定规划松弛模型：
\[\begin{aligned} \min \quad & \sum_{i=1}^n w_i Y_{0i} \\ \text{s.t.} \quad & Y_{0i} + \sum_{j \in N(i)} Y_{0j} \geq 1, \quad \forall i \in V \\ & Y_{ii} = Y_{0i}, \quad \forall i \in V \\ & Y_{00} = 1 \\ & Y \succeq 0 \\ & Y_{0i} \geq 0, \quad \forall i \in V \end{aligned} \]
这里 \(Y \succeq 0\) 表示矩阵 \(Y\) 是半正定的。注意，原始整数约束 \(x_i \in \{0, 1\}\) 已被松弛为连续约束。
4. 求解半定规划并舍入得到整数解
半定规划可以在多项式时间内求解至任意精度（例如使用内点法），得到最优解矩阵 \(Y^*\)。从 \(Y^*\) 我们可以通过Cholesky分解或特征分解得到一组向量 \(\mathbf{v}_0^*, \mathbf{v}_1^*, \dots, \mathbf{v}_n^*\)（满足 \(Y_{ij}^* = \mathbf{v}_i^* \cdot \mathbf{v}_j^*\)）。
现在我们需要将向量解舍入为0-1整数解 \(\hat{x}_i \in \{0, 1\}\)。这里介绍一种常用的随机舍入方法：
4.1 随机超平面舍入
- 随机生成一个单位向量 \(\mathbf{r} \in \mathbb{R}^{n+1}\)（服从均匀分布）。
- 对于每个顶点 \(i\)，我们计算 \(\mathbf{v}_i^* \cdot \mathbf{r}\)。
- 舍入规则：如果 \(\mathbf{v}_i^* \cdot \mathbf{r} \geq \mathbf{v}_0^* \cdot \mathbf{r}\)，则令 \(\hat{x}_i = 1\)；否则 \(\hat{x}_i = 0\)。
几何解释：我们以 \(\mathbf{v}_0^*\) 为界，将所有向量投影到随机方向 \(\mathbf{r}\) 上，若投影值大于等于 \(\mathbf{v}_0^*\) 的投影，则选择该顶点。
4.2 保证支配约束
上述简单舍入可能无法保证得到的集合一定是支配集。因此，我们需要一个后处理步骤：
检查每个顶点 \(i\)：
- 如果 \(i\) 本身被选中（\(\hat{x}_i = 1\)），或者其某个邻居被选中，则 \(i\) 已被支配。
- 否则，我们强制选择 \(i\) 本身（设 \(\hat{x}_i = 1\)），以满足支配约束。
5. 算法流程总结
- 输入：图 \(G = (V, E)\)，顶点权重 \(w_i\)。
- 建模：建立上述半定规划松弛模型。
- 求解SDP：调用半定规划求解器，得到最优解矩阵 \(Y^*\) 和向量 \(\mathbf{v}_i^*\)。
- 随机舍入：生成随机向量 \(\mathbf{r}\)，根据 \(\mathbf{v}_i^* \cdot \mathbf{r}\) 与 \(\mathbf{v}_0^* \cdot \mathbf{r}\) 的比较，初步确定 \(\hat{x}_i\)。
- 后处理：检查所有顶点，若某个顶点未被支配，则将其加入支配集。
- 输出：支配集 \(S = \{ i \mid \hat{x}_i = 1 \}\) 及其总权重。
6. 性能分析
- 近似比：对于最小权支配集问题，基于半定规划松弛的随机舍入算法可以达到 \(O(\log n)\) 的近似比（在某些图类中可能更好）。这是因为后处理步骤可能增加一些顶点，但通过概率分析可以证明期望权重不会太大。
- 时间复杂度：求解半定规划是多项式时间的，但通常比线性规划慢。随机舍入和后处理步骤可以在 \(O(n + m)\) 时间内完成（\(m\) 为边数）。
7. 实例演示（小图）
考虑一个简单图：顶点集 \(V = \{1, 2, 3\}\)，边 \(E = \{(1,2), (2,3)\}\)，权重 \(w_1 = 2, w_2 = 1, w_3 = 3\)。
-
整数规划模型：
- 约束：
\(x_1 + x_2 \geq 1\)（顶点1）
\(x_2 + x_1 + x_3 \geq 1\)（顶点2）
\(x_3 + x_2 \geq 1\)（顶点3） - 目标：最小化 \(2x_1 + x_2 + 3x_3\)。
最优整数解为 \(x_2 = 1\)，其他为0，权重为1。
- 约束：
-
SDP松弛求解（省略数值求解步骤）：得到 \(Y_{01}, Y_{02}, Y_{03}\) 的值可能接近0.5左右（满足约束且最小化权重）。
-
舍入：若随机向量导致 \(\hat{x}_2 = 1\)，则已满足支配条件，输出权重1；若其他情况，后处理可能增加顶点，但期望权重可通过概率分析控制在 \(O(\log 3) \cdot \text{OPT}\) 范围内。
通过这个例子，您可以看到从整数模型到SDP松弛，再到舍入算法的完整流程。这种方法能够处理大规模图的最小权支配集问题，并提供理论性能保证。