基于线性规划的图最小控制集问题的半定规划松弛求解示例
字数 4622 2025-12-07 17:47:20

基于线性规划的图最小控制集问题的半定规划松弛求解示例

题目描述
考虑一个无向图 \(G = (V, E)\)，其中 \(V = \{1, 2, ..., n\}\) 是顶点集，\(E\) 是边集。一个控制集（Dominating Set）是顶点集的一个子集 \(S \subseteq V\)，使得图中每个顶点要么在 \(S\) 中，要么至少与 \(S\) 中的一个顶点相邻。图的最小控制集问题要求找到一个顶点数最少（即 \(|S|\) 最小）的控制集。这是一个经典的NP-hard组合优化问题。本题目要求：首先为该问题建立一个整数规划模型，然后利用半定规划松弛技术构造一个松弛模型，并设计舍入算法从松弛解中恢复出一个可行的控制集，最后分析该算法的近似比。

解题过程
我将循序渐进地分步讲解，从建模、松弛到算法设计及分析。

1. 整数规划建模

为每个顶点 \(i \in V\) 引入一个0-1决策变量 \(x_i\)：

  • \(x_i = 1\) 表示顶点 \(i\) 被选入控制集 \(S\)，
  • \(x_i = 0\) 表示不被选中。

目标：最小化选中的顶点数，即 \(\sum_{i=1}^n x_i\)。

约束：每个顶点必须被控制，即对任意顶点 \(j \in V\)，要么 \(j\) 自身被选中（\(x_j = 1\)），要么至少有一个邻居被选中。形式化地，对每个 \(j \in V\)：

\[x_j + \sum_{i \in N(j)} x_i \ge 1 \]

其中 \(N(j)\) 表示顶点 \(j\) 的邻居集合（不包括 \(j\) 自身）。

于是得到整数规划模型：

\[\begin{aligned} \min \quad & \sum_{i=1}^n x_i \\ \text{s.t.} \quad & x_j + \sum_{i \in N(j)} x_i \ge 1, \quad \forall j \in V \\ & x_i \in \{0,1\}, \quad \forall i \in V \end{aligned} \]

由于是NP-hard，直接求解困难，我们转向松弛方法。

2. 半定规划松弛的构造

半定规划是线性规划的推广，允许变量为一个半正定矩阵。我们分两步构造松弛。

步骤1：转化为二次规划
引入向量变量 \(v_i \in \mathbb{R}^{n+1}\)，并定义：

\[v_i = \begin{bmatrix} x_i \\ y_i \end{bmatrix}, \quad i=1,\dots,n \]

并增加一个辅助向量 \(v_0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}\)（固定）。

我们想要满足：

  1. \(x_i \in \{0,1\}\) 等价于 \(x_i^2 = x_i\)。
  2. 约束 \(x_j + \sum_{i \in N(j)} x_i \ge 1\) 是线性的，可直接用向量内积表示。

一个技巧是：定义矩阵 \(X = V^\top V\)，其中 \(V\) 是以 \(v_0, v_1, \dots, v_n\) 为列的矩阵。则 \(X\) 是 \((n+1) \times (n+1)\) 的对称半正定矩阵，且满足 \(X_{00} = 1\)（因为 \(v_0\) 固定），且对角元 \(X_{ii} = \|v_i\|^2\)。

步骤2：建立半定规划模型
令 \(e_i\) 表示第 \(i\) 个单位向量（维数 \(n+1\)，从0开始标号）。则：

  • \(x_i = v_0^\top v_i = e_0^\top X e_i\)。
  • 约束 \(x_j + \sum_{i \in N(j)} x_i \ge 1\) 可写成：

\[e_0^\top X e_j + \sum_{i \in N(j)} e_0^\top X e_i \ge 1 \]

等价于：

\[e_0^\top X \left( e_j + \sum_{i \in N(j)} e_i \right) \ge 1 \]

定义向量 \(d_j = e_j + \sum_{i \in N(j)} e_i\)，则约束为 \(e_0^\top X d_j \ge 1\)。

目标函数为 \(\sum_i x_i = \sum_i e_0^\top X e_i = e_0^\top X \left( \sum_i e_i \right)\)。

另外，我们需要加强条件以保证解的质量。常用技巧是增加约束 \(X_{ii} = X_{0i}\)（因为 \(x_i^2 = x_i\) 在0-1情形成立，松弛为 \(X_{ii} = X_{0i}\)）。这样得到半定规划松弛：

\[\begin{aligned} \min \quad & e_0^\top X \left( \sum_{i=1}^n e_i \right) \\ \text{s.t.} \quad & e_0^\top X d_j \ge 1, \quad \forall j \in V \\ & X_{0i} = X_{ii}, \quad \forall i=1,\dots,n \\ & X_{00} = 1 \\ & X \succeq 0 \quad (\text{半正定}) \end{aligned} \]

这是一个凸优化问题，可在多项式时间内求解。

3. 舍入算法设计

设已求得半定规划的最优解 \(X^*\)，其秩可能大于1。通过Cholesky分解可得向量 \(v_0, v_1, \dots, v_n \in \mathbb{R}^{n+1}\) 满足 \(X_{ij}^* = v_i^\top v_j\)，且 \(v_0\) 固定为 \([1,0,\dots,0]^\top\)。由于 \(X_{0i}^* = X_{ii}^*\)，有 \(v_0^\top v_i = \|v_i\|^2\)，记 \(x_i^* = v_0^\top v_i = \|v_i\|^2 \in [0,1]\)。

随机舍入算法（基于超平面舍入）：

  1. 随机生成一个单位向量 \(r \in \mathbb{R}^{n+1}\)（服从均匀分布）。
  2. 对每个顶点 \(i = 1,\dots,n\)：
    • 若 \(v_0^\top v_i \ge \alpha \, v_i^\top r\) 对某个固定参数 \(\alpha > 0\) 成立，则将 \(i\) 加入控制集 \(S\)。
      更常见的一种等价形式是：定义 \(u_i = v_i - \frac{1}{2} v_0\)，然后根据 \(r^\top u_i\) 的符号决定。但为简单起见，这里采用一种更直接的舍入：
      由于 \(v_0\) 固定，考虑随机超平面法：若 \(\text{sign}(r^\top v_i) = \text{sign}(r^\top v_0)\)，则舍入为1，但这样不直接保证控制性质。
      改进的舍入策略：
    • 对每个顶点 \(j\)，若其自身或某个邻居满足 \(v_j^\top r \ge \theta\)（\(\theta\) 为阈值），则将该邻居或自身选入。但需调整以保证可行性。

实践中常用以下简单舍入：

  1. 随机选取单位向量 \(r\)。
  2. 计算 \(s_i = v_0^\top v_i + \beta (v_i^\top r)\)，其中 \(\beta\) 是缩放参数。
  3. 选择所有满足 \(s_i \ge t\) 的顶点 \(i\)，其中 \(t\) 是阈值。
    然后验证控制性质，若不满足，则对未覆盖的顶点直接将其自身加入 \(S\)。

简化确定性舍入（便于分析）：
由于 \(v_0^\top v_i = \|v_i\|^2\)，且 \(v_0^\top (v_i + \sum_{k \in N(i)} v_k) \ge 1\)，可知至少有一个 \(v_j\)（\(j = i\) 或邻居）满足 \(\|v_j\|^2 \ge \frac{1}{\deg(i)+1}\)。
我们可设置阈值 \(\tau = \frac{1}{\Delta+1}\)（\(\Delta\) 为最大度），然后选择所有满足 \(\|v_i\|^2 \ge \tau\) 的顶点 \(i\)。这样可保证控制性质：
对任意顶点 \(j\)，若 \(\|v_j\|^2 \ge \tau\)，则 \(j\) 自身被选；否则，约束条件 \(v_0^\top v_j + \sum_{k \in N(j)} v_0^\top v_k \ge 1\) 意味着存在邻居 \(k\) 使得 \(\|v_k\|^2 \ge \frac{1}{\deg(j)+1} \ge \tau\)，因此该邻居被选。于是得到可行控制集。

4. 近似比分析

设半定规划最优值为 \(\text{SDP}^* = \sum_{i=1}^n \|v_i\|^2\)。算法选择的顶点满足 \(\|v_i\|^2 \ge \tau = \frac{1}{\Delta+1}\)。

控制集大小上界：
对每个被选顶点 \(i\)，有 \(\|v_i\|^2 \ge \tau\)，所以算法解的大小 \(|S| \le \frac{\sum_{i=1}^n \|v_i\|^2}{\tau} = \text{SDP}^* \cdot (\Delta+1)\)。

由于整数最优解 \(\text{OPT} \ge \text{SDP}^*\)（因为半定规划是松弛），我们得到：

\[|S| \le (\Delta+1) \cdot \text{OPT} \]

即这是一个 \((\Delta+1)\)-近似算法。对一般图，\(\Delta\) 可能很大，但在稀疏图上效果好。

可进一步改进：利用随机舍入和概率分析，可获得 \(O(\log \Delta)\) 的近似比，但推导更复杂，这里略过。

5. 总结

本题目展示了如何将最小控制集问题转化为半定规划松弛，并利用简单的阈值舍入得到可行解。该方法的关键在于利用向量表示和半正定约束捕捉问题的组合结构，从而获得比线性规划松弛更紧的界。虽然近似比依赖最大度，但为NP-hard问题提供了有效的近似方案。

基于线性规划的图最小控制集问题的半定规划松弛求解示例 题目描述 考虑一个无向图 \( G = (V, E) \)，其中 \( V = \{1, 2, ..., n\} \) 是顶点集，\( E \) 是边集。一个控制集（Dominating Set）是顶点集的一个子集 \( S \subseteq V \)，使得图中每个顶点要么在 \( S \) 中，要么至少与 \( S \) 中的一个顶点相邻。图的最小控制集问题要求找到一个顶点数最少（即 \( |S| \) 最小）的控制集。这是一个经典的NP-hard组合优化问题。本题目要求：首先为该问题建立一个整数规划模型，然后利用半定规划松弛技术构造一个松弛模型，并设计舍入算法从松弛解中恢复出一个可行的控制集，最后分析该算法的近似比。 解题过程 我将循序渐进地分步讲解，从建模、松弛到算法设计及分析。 1. 整数规划建模 为每个顶点 \( i \in V \) 引入一个0-1决策变量 \( x_ i \)： \( x_ i = 1 \) 表示顶点 \( i \) 被选入控制集 \( S \)， \( x_ i = 0 \) 表示不被选中。 目标 ：最小化选中的顶点数，即 \( \sum_ {i=1}^n x_ i \)。 约束 ：每个顶点必须被控制，即对任意顶点 \( j \in V \)，要么 \( j \) 自身被选中（\( x_ j = 1 \)），要么至少有一个邻居被选中。形式化地，对每个 \( j \in V \)： \[ x_ j + \sum_ {i \in N(j)} x_ i \ge 1 \] 其中 \( N(j) \) 表示顶点 \( j \) 的邻居集合（不包括 \( j \) 自身）。 于是得到整数规划模型： \[ \begin{aligned} \min \quad & \sum_ {i=1}^n x_ i \\ \text{s.t.} \quad & x_ j + \sum_ {i \in N(j)} x_ i \ge 1, \quad \forall j \in V \\ & x_ i \in \{0,1\}, \quad \forall i \in V \end{aligned} \] 由于是NP-hard，直接求解困难，我们转向松弛方法。 2. 半定规划松弛的构造 半定规划是线性规划的推广，允许变量为一个半正定矩阵。我们分两步构造松弛。 步骤1：转化为二次规划 引入向量变量 \( v_ i \in \mathbb{R}^{n+1} \)，并定义： \[ v_ i = \begin{bmatrix} x_ i \\ y_ i \end{bmatrix}, \quad i=1,\dots,n \] 并增加一个辅助向量 \( v_ 0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix} \)（固定）。 我们想要满足： \( x_ i \in \{0,1\} \) 等价于 \( x_ i^2 = x_ i \)。 约束 \( x_ j + \sum_ {i \in N(j)} x_ i \ge 1 \) 是线性的，可直接用向量内积表示。 一个技巧是：定义矩阵 \( X = V^\top V \)，其中 \( V \) 是以 \( v_ 0, v_ 1, \dots, v_ n \) 为列的矩阵。则 \( X \) 是 \( (n+1) \times (n+1) \) 的对称半正定矩阵，且满足 \( X_ {00} = 1 \)（因为 \( v_ 0 \) 固定），且对角元 \( X_ {ii} = \|v_ i\|^2 \)。 步骤2：建立半定规划模型 令 \( e_ i \) 表示第 \( i \) 个单位向量（维数 \( n+1 \)，从0开始标号）。则： \( x_ i = v_ 0^\top v_ i = e_ 0^\top X e_ i \)。 约束 \( x_ j + \sum_ {i \in N(j)} x_ i \ge 1 \) 可写成： \[ e_ 0^\top X e_ j + \sum_ {i \in N(j)} e_ 0^\top X e_ i \ge 1 \] 等价于： \[ e_ 0^\top X \left( e_ j + \sum_ {i \in N(j)} e_ i \right) \ge 1 \] 定义向量 \( d_ j = e_ j + \sum_ {i \in N(j)} e_ i \)，则约束为 \( e_ 0^\top X d_ j \ge 1 \)。 目标函数为 \( \sum_ i x_ i = \sum_ i e_ 0^\top X e_ i = e_ 0^\top X \left( \sum_ i e_ i \right) \)。 另外，我们需要加强条件以保证解的质量。常用技巧是增加约束 \( X_ {ii} = X_ {0i} \)（因为 \( x_ i^2 = x_ i \) 在0-1情形成立，松弛为 \( X_ {ii} = X_ {0i} \)）。这样得到 半定规划松弛 ： \[ \begin{aligned} \min \quad & e_ 0^\top X \left( \sum_ {i=1}^n e_ i \right) \\ \text{s.t.} \quad & e_ 0^\top X d_ j \ge 1, \quad \forall j \in V \\ & X_ {0i} = X_ {ii}, \quad \forall i=1,\dots,n \\ & X_ {00} = 1 \\ & X \succeq 0 \quad (\text{半正定}) \end{aligned} \] 这是一个凸优化问题，可在多项式时间内求解。 3. 舍入算法设计 设已求得半定规划的最优解 \( X^* \)，其秩可能大于1。通过Cholesky分解可得向量 \( v_ 0, v_ 1, \dots, v_ n \in \mathbb{R}^{n+1} \) 满足 \( X_ {ij}^* = v_ i^\top v_ j \)，且 \( v_ 0 \) 固定为 \( [ 1,0,\dots,0]^\top \)。由于 \( X_ {0i}^* = X_ {ii}^* \)，有 \( v_ 0^\top v_ i = \|v_ i\|^2 \)，记 \( x_ i^* = v_ 0^\top v_ i = \|v_ i\|^2 \in [ 0,1 ] \)。 随机舍入算法 （基于超平面舍入）： 随机生成一个单位向量 \( r \in \mathbb{R}^{n+1} \)（服从均匀分布）。 对每个顶点 \( i = 1,\dots,n \)： 若 \( v_ 0^\top v_ i \ge \alpha \, v_ i^\top r \) 对某个固定参数 \( \alpha > 0 \) 成立，则将 \( i \) 加入控制集 \( S \)。 更常见的一种等价形式是：定义 \( u_ i = v_ i - \frac{1}{2} v_ 0 \)，然后根据 \( r^\top u_ i \) 的符号决定。但为简单起见，这里采用一种更直接的舍入： 由于 \( v_ 0 \) 固定，考虑随机超平面法：若 \( \text{sign}(r^\top v_ i) = \text{sign}(r^\top v_ 0) \)，则舍入为1，但这样不直接保证控制性质。 改进的舍入策略： 对每个顶点 \( j \)，若其自身或某个邻居满足 \( v_ j^\top r \ge \theta \)（\( \theta \) 为阈值），则将该邻居或自身选入。但需调整以保证可行性。 实践中常用以下简单舍入： 随机选取单位向量 \( r \)。 计算 \( s_ i = v_ 0^\top v_ i + \beta (v_ i^\top r) \)，其中 \( \beta \) 是缩放参数。 选择所有满足 \( s_ i \ge t \) 的顶点 \( i \)，其中 \( t \) 是阈值。 然后验证控制性质，若不满足，则对未覆盖的顶点直接将其自身加入 \( S \)。 简化确定性舍入 （便于分析）： 由于 \( v_ 0^\top v_ i = \|v_ i\|^2 \)，且 \( v_ 0^\top (v_ i + \sum_ {k \in N(i)} v_ k) \ge 1 \)，可知至少有一个 \( v_ j \)（\( j = i \) 或邻居）满足 \( \|v_ j\|^2 \ge \frac{1}{\deg(i)+1} \)。 我们可设置阈值 \( \tau = \frac{1}{\Delta+1} \)（\( \Delta \) 为最大度），然后选择所有满足 \( \|v_ i\|^2 \ge \tau \) 的顶点 \( i \)。这样可保证控制性质： 对任意顶点 \( j \)，若 \( \|v_ j\|^2 \ge \tau \)，则 \( j \) 自身被选；否则，约束条件 \( v_ 0^\top v_ j + \sum_ {k \in N(j)} v_ 0^\top v_ k \ge 1 \) 意味着存在邻居 \( k \) 使得 \( \|v_ k\|^2 \ge \frac{1}{\deg(j)+1} \ge \tau \)，因此该邻居被选。于是得到可行控制集。 4. 近似比分析 设半定规划最优值为 \( \text{SDP}^* = \sum_ {i=1}^n \|v_ i\|^2 \)。算法选择的顶点满足 \( \|v_ i\|^2 \ge \tau = \frac{1}{\Delta+1} \)。 控制集大小上界 ： 对每个被选顶点 \( i \)，有 \( \|v_ i\|^2 \ge \tau \)，所以算法解的大小 \( |S| \le \frac{\sum_ {i=1}^n \|v_ i\|^2}{\tau} = \text{SDP}^* \cdot (\Delta+1) \)。 由于整数最优解 \( \text{OPT} \ge \text{SDP}^* \)（因为半定规划是松弛），我们得到： \[ |S| \le (\Delta+1) \cdot \text{OPT} \] 即这是一个 \( (\Delta+1) \)-近似算法。对一般图，\( \Delta \) 可能很大，但在稀疏图上效果好。 可进一步改进：利用随机舍入和概率分析，可获得 \( O(\log \Delta) \) 的近似比，但推导更复杂，这里略过。 5. 总结 本题目展示了如何将最小控制集问题转化为半定规划松弛，并利用简单的阈值舍入得到可行解。该方法的关键在于利用向量表示和半正定约束捕捉问题的组合结构，从而获得比线性规划松弛更紧的界。虽然近似比依赖最大度，但为NP-hard问题提供了有效的近似方案。