基于线性规划的图最大权独立集问题求解示例 题目描述 在图 \( G = (V, E) \) 中，每个顶点 \( v \in V \) 有一个权重 \( w_ v \geq 0 \)。 最大权独立集问题 要求选择一个顶点子集 \( S \subseteq V \)，使得 \( S \) 中任意两个顶点不相邻（即没有边连接），且顶点权重之和 \( \sum_ {v \in S} w_ v \) 最大。该问题是NP难问题，但可以通过线性规划松弛和舍入策略得到近似解。 解题过程 1. 问题建模为整数规划 定义二元变量 \( x_ v \in \{0, 1\} \) 表示顶点 \( v \) 是否被选入独立集： \[ x_ v = \begin{cases} 1 & \text{若 } v \in S \\ 0 & \text{否则} \end{cases} \] 目标函数和约束条件如下： \[ \text{最大化} \quad \sum_ {v \in V} w_ v x_ v \] \[ \text{约束} \quad x_ u + x_ v \leq 1 \quad \forall (u, v) \in E \] \[ x_ v \in \{0, 1\} \quad \forall v \in V \] 边约束保证相邻顶点不同时被选。 2. 线性规划松弛 将整数约束松弛为连续变量： \[ \text{最大化} \quad \sum_ {v \in V} w_ v x_ v \] \[ \text{约束} \quad x_ u + x_ v \leq 1 \quad \forall (u, v) \in E \] \[ 0 \leq x_ v \leq 1 \quad \forall v \in V \] 该线性规划的最优值是其整数规划最优值的上界。 3. 求解线性规划 使用单纯形法或内点法求解松弛问题，得到最优解 \( x^* \)。由于约束矩阵是边-顶点关联矩阵（全单模性不成立），解可能是分数。 4. 随机化舍入策略 设计随机算法将分数解转化为整数解： 以概率 \( x_ v^* \) 独立地将每个顶点 \( v \) 选入集合 \( S' \)。 但 \( S' \) 可能包含相邻顶点，需修正：若一条边的两个端点均被选中，则随机丢弃其中一个。 5. 近似比分析 期望权重和： \[ \mathbb{E}[ \sum_ {v \in S'} w_ v] = \sum_ {v \in V} w_ v x_ v^* \] 考虑边 \( (u, v) \) 冲突的概率为 \( x_ u^* x_ v^* \)。修正后，至少保留一个顶点的概率为 \( 1 - (1 - x_ u^ )(1 - x_ v^ ) \)。 通过条件期望或贪婪修正可证明，最终独立集 \( S \) 的期望权重至少为 \( \frac{1}{2} \sum w_ v x_ v^* \)，即 近似比至少为 1/2 。 6. 改进策略 对于无环图（如二分图），可通过动态规划精确求解；一般图可结合分支定界或半定规划松弛（如Lovász theta函数）得到更紧的界。 关键点总结 整数规划模型是核心，边约束确保独立性。 线性规划松弛提供上界，随机舍入保证近似解的质量。 该方法适用于大规模图，且可扩展至带权约束的变种问题。