基于线性规划的图最大权匹配问题的半定规划松弛与舍入算法求解示例
字数 3407 2025-12-20 23:08:18

基于线性规划的图最大权匹配问题的半定规划松弛与舍入算法求解示例

1. 问题描述

我们考虑一个无向图 \(G=(V, E)\)，其中每条边 \(e \in E\) 有一个非负权重 \(w_e\)。一个匹配是边集的一个子集，使得其中任意两条边没有公共顶点。最大权匹配问题是寻找一个匹配，使得所选边的权重之和最大。这是一个经典的组合优化问题，在二分图上有多项式时间算法（如匈牙利算法），但在一般图上求解最大权匹配是一个NP难问题。因此，我们寻求近似算法。本示例介绍一种基于半定规划松弛的随机舍入算法，该算法能达到近似比约0.5。

2. 整数规划模型

首先，我们为最大权匹配问题建立一个整数线性规划模型。引入变量 \(x_e \in \{0,1\}\) 表示边 \(e\) 是否被选入匹配。由于匹配中每个顶点最多关联一条边，因此对于每个顶点 \(v\)，其关联边中至多有一条被选中。于是，整数规划模型如下：

目标函数：最大化 \(\sum_{e \in E} w_e x_e\)

约束条件：

  1. 对于每个顶点 \(v \in V\)：\(\sum_{e \in \delta(v)} x_e \leq 1\)，其中 \(\delta(v)\) 表示与 \(v\) 关联的边集合。
  2. 对于每条边 \(e \in E\)：\(x_e \in \{0,1\}\)。

这是一个整数线性规划，但由于它描述的是匹配问题，其线性规划松弛的最优解不一定是整数（即存在分数解）。因此，直接对线性规划松弛进行舍入可能无法得到高质量的近似解。于是，我们转向一种更强的松弛：半定规划松弛。

3. 半定规划松弛

半定规划（SDP）是线性规划的一种推广，允许变量为半正定矩阵。为了构建半定规划松弛，我们为每个顶点 \(v \in V\) 分配一个单位向量 \(\mathbf{u}_v \in \mathbb{R}^n\)（其中 \(n = |V|\)）。对于每条边 \(e = (u, v)\)，我们希望用向量 \(\mathbf{u}_u\) 和 \(\mathbf{u}_v\) 的内积来表示匹配变量。具体来说，我们定义 \(x_e = \frac{1 - \mathbf{u}_u \cdot \mathbf{u}_v}{2}\)。注意：如果 \(\mathbf{u}_u = \mathbf{u}_v\)，则 \(x_e = 0\)；如果 \(\mathbf{u}_u = -\mathbf{u}_v\)，则 \(x_e = 1\)。因此，\(x_e\) 可以理解为边 \(e\) 被选中的“概率”或“程度”。

基于此，我们可以将整数规划约束转化为向量约束。首先，对于每个顶点 \(v\)，其关联边被选中的总和约束 \(\sum_{e \in \delta(v)} x_e \leq 1\) 可以推导为：

\[\sum_{e \in \delta(v)} \frac{1 - \mathbf{u}_u \cdot \mathbf{u}_v}{2} \leq 1 \quad \Rightarrow \quad \sum_{e \in \delta(v)} (1 - \mathbf{u}_u \cdot \mathbf{u}_v) \leq 2. \]

此外，我们要求所有向量都是单位向量：\(\|\mathbf{u}_v\|^2 = 1\) 对所有 \(v \in V\) 成立。

因此，半定规划松弛模型如下：

目标函数：最大化 \(\sum_{e = (u,v) \in E} w_e \cdot \frac{1 - \mathbf{u}_u \cdot \mathbf{u}_v}{2}\)

约束条件：

  1. 对于每个顶点 \(v \in V\)：\(\sum_{e = (u,v) \in E} (1 - \mathbf{u}_u \cdot \mathbf{u}_v) \leq 2\)。
  2. 对于所有 \(v \in V\)：\(\|\mathbf{u}_v\|^2 = 1\)。
  3. 所有向量 \(\mathbf{u}_v\) 为实向量。

这是一个半定规划问题，可以通过内点法在多项式时间内求解，得到一组最优向量 \(\{\mathbf{u}_v^*\}_{v \in V}\)。

4. 随机舍入算法

得到最优向量后，我们需要将它们舍入为一个整数解（即一个匹配）。这里介绍一种简单的随机舍入算法：

  1. 随机选择一个单位向量 \(\mathbf{r} \in \mathbb{R}^n\)（从均匀分布的单位球面上随机选取）。
  2. 对于每个顶点 \(v \in V\)，计算其投影值 \(s_v = \mathbf{u}_v^* \cdot \mathbf{r}\)。
  3. 将顶点按照 \(s_v\) 的值从小到大排序。
  4. 依次处理排序后的顶点：对于当前顶点 \(v\)，如果它尚未被匹配，则检查其邻居中尚未被匹配且 \(s_u\) 值与 \(s_v\) 最接近的顶点 \(u\)。如果边 \((u, v)\) 存在，则将 \((u, v)\) 加入匹配，并标记 \(u\) 和 \(v\) 为已匹配。

这个算法的思想是：如果两个顶点 \(u\) 和 \(v\) 对应的向量 \(\mathbf{u}_u^*\) 和 \(\mathbf{u}_v^*\) 方向相反（即 \(\mathbf{u}_u^* \cdot \mathbf{u}_v^*\) 接近 -1），那么它们被投影到随机方向 \(\mathbf{r}\) 上的值 \(s_u\) 和 \(s_v\) 很可能符号相反且绝对值较大，从而在排序中可能被分离开，增加了它们被匹配的可能性。

5. 算法性能分析

可以证明，对于每条边 \(e = (u,v)\)，其被算法选入匹配的概率至少为 \(\frac{1}{4} \cdot (1 - \mathbf{u}_u^* \cdot \mathbf{u}_v^*)\)。因此，算法的期望权重至少为：

\[\mathbb{E}[\text{算法输出权重}] \geq \sum_{e \in E} w_e \cdot \frac{1}{4} \cdot (1 - \mathbf{u}_u^* \cdot \mathbf{u}_v^*) = \frac{1}{2} \cdot \text{SDP最优值}. \]

由于SDP最优值是原整数规划最优值的一个上界（因为SDP是原问题的松弛），因此算法达到了至少0.5的近似比。

6. 举例说明

假设有一个三角形图（三个顶点 \(a, b, c\)，三条边 \(ab, bc, ca\)），权重均为1。整数最优解是选择任意一条边（权重1）。SDP松弛可能给出向量解：例如，取三个互成120°角的单位向量 \(\mathbf{u}_a, \mathbf{u}_b, \mathbf{u}_c\)，则每条边的 \(\frac{1 - \mathbf{u}_u \cdot \mathbf{u}_v}{2} = \frac{1 - (-\frac{1}{2})}{2} = \frac{3}{4}\)，SDP目标值为 \(3 \times \frac{3}{4} = 2.25\)。随机舍入算法以一定概率输出一条边（期望权重至少为 \(0.5 \times 2.25 = 1.125\)），但实际匹配最多一条边，所以期望权重为1，仍然满足近似比0.5。

7. 总结

本示例展示了如何将最大权匹配问题松弛为半定规划，并利用随机舍入得到近似解。该方法的核心在于利用向量几何关系来捕捉匹配的“冲突”约束，并通过随机投影将连续解舍入为整数解。虽然近似比为0.5，不如二分图上的精确算法，但在一般图上这是一种有效的近似方法。

基于线性规划的图最大权匹配问题的半定规划松弛与舍入算法求解示例 1. 问题描述 我们考虑一个无向图 \( G=(V, E) \)，其中每条边 \( e \in E \) 有一个非负权重 \( w_ e \)。一个匹配是边集的一个子集，使得其中任意两条边没有公共顶点。最大权匹配问题是寻找一个匹配，使得所选边的权重之和最大。这是一个经典的组合优化问题，在二分图上有多项式时间算法（如匈牙利算法），但在一般图上求解最大权匹配是一个NP难问题。因此，我们寻求近似算法。本示例介绍一种基于半定规划松弛的随机舍入算法，该算法能达到近似比约0.5。 2. 整数规划模型 首先，我们为最大权匹配问题建立一个整数线性规划模型。引入变量 \( x_ e \in \{0,1\} \) 表示边 \( e \) 是否被选入匹配。由于匹配中每个顶点最多关联一条边，因此对于每个顶点 \( v \)，其关联边中至多有一条被选中。于是，整数规划模型如下： 目标函数 ：最大化 \( \sum_ {e \in E} w_ e x_ e \) 约束条件 ： 对于每个顶点 \( v \in V \)：\( \sum_ {e \in \delta(v)} x_ e \leq 1 \)，其中 \( \delta(v) \) 表示与 \( v \) 关联的边集合。 对于每条边 \( e \in E \)：\( x_ e \in \{0,1\} \)。 这是一个整数线性规划，但由于它描述的是匹配问题，其线性规划松弛的最优解不一定是整数（即存在分数解）。因此，直接对线性规划松弛进行舍入可能无法得到高质量的近似解。于是，我们转向一种更强的松弛：半定规划松弛。 3. 半定规划松弛 半定规划（SDP）是线性规划的一种推广，允许变量为半正定矩阵。为了构建半定规划松弛，我们为每个顶点 \( v \in V \) 分配一个单位向量 \( \mathbf{u}_ v \in \mathbb{R}^n \)（其中 \( n = |V| \)）。对于每条边 \( e = (u, v) \)，我们希望用向量 \( \mathbf{u}_ u \) 和 \( \mathbf{u}_ v \) 的内积来表示匹配变量。具体来说，我们定义 \( x_ e = \frac{1 - \mathbf{u}_ u \cdot \mathbf{u}_ v}{2} \)。注意：如果 \( \mathbf{u}_ u = \mathbf{u}_ v \)，则 \( x_ e = 0 \)；如果 \( \mathbf{u}_ u = -\mathbf{u}_ v \)，则 \( x_ e = 1 \)。因此，\( x_ e \) 可以理解为边 \( e \) 被选中的“概率”或“程度”。 基于此，我们可以将整数规划约束转化为向量约束。首先，对于每个顶点 \( v \)，其关联边被选中的总和约束 \( \sum_ {e \in \delta(v)} x_ e \leq 1 \) 可以推导为： \[ \sum_ {e \in \delta(v)} \frac{1 - \mathbf{u}_ u \cdot \mathbf{u} v}{2} \leq 1 \quad \Rightarrow \quad \sum {e \in \delta(v)} (1 - \mathbf{u}_ u \cdot \mathbf{u}_ v) \leq 2. \] 此外，我们要求所有向量都是单位向量：\( \|\mathbf{u}_ v\|^2 = 1 \) 对所有 \( v \in V \) 成立。 因此，半定规划松弛模型如下： 目标函数 ：最大化 \( \sum_ {e = (u,v) \in E} w_ e \cdot \frac{1 - \mathbf{u}_ u \cdot \mathbf{u}_ v}{2} \) 约束条件 ： 对于每个顶点 \( v \in V \)：\( \sum_ {e = (u,v) \in E} (1 - \mathbf{u}_ u \cdot \mathbf{u}_ v) \leq 2 \)。 对于所有 \( v \in V \)：\( \|\mathbf{u}_ v\|^2 = 1 \)。 所有向量 \( \mathbf{u}_ v \) 为实向量。 这是一个半定规划问题，可以通过内点法在多项式时间内求解，得到一组最优向量 \( \{\mathbf{u} v^* \} {v \in V} \)。 4. 随机舍入算法 得到最优向量后，我们需要将它们舍入为一个整数解（即一个匹配）。这里介绍一种简单的随机舍入算法： 随机选择一个单位向量 \( \mathbf{r} \in \mathbb{R}^n \)（从均匀分布的单位球面上随机选取）。 对于每个顶点 \( v \in V \)，计算其投影值 \( s_ v = \mathbf{u}_ v^* \cdot \mathbf{r} \)。 将顶点按照 \( s_ v \) 的值从小到大排序。 依次处理排序后的顶点：对于当前顶点 \( v \)，如果它尚未被匹配，则检查其邻居中尚未被匹配且 \( s_ u \) 值与 \( s_ v \) 最接近的顶点 \( u \)。如果边 \( (u, v) \) 存在，则将 \( (u, v) \) 加入匹配，并标记 \( u \) 和 \( v \) 为已匹配。 这个算法的思想是：如果两个顶点 \( u \) 和 \( v \) 对应的向量 \( \mathbf{u}_ u^* \) 和 \( \mathbf{u}_ v^* \) 方向相反（即 \( \mathbf{u}_ u^* \cdot \mathbf{u}_ v^* \) 接近 -1），那么它们被投影到随机方向 \( \mathbf{r} \) 上的值 \( s_ u \) 和 \( s_ v \) 很可能符号相反且绝对值较大，从而在排序中可能被分离开，增加了它们被匹配的可能性。 5. 算法性能分析 可以证明，对于每条边 \( e = (u,v) \)，其被算法选入匹配的概率至少为 \( \frac{1}{4} \cdot (1 - \mathbf{u}_ u^* \cdot \mathbf{u} v^* ) \)。因此，算法的期望权重至少为： \[ \mathbb{E}[ \text{算法输出权重}] \geq \sum {e \in E} w_ e \cdot \frac{1}{4} \cdot (1 - \mathbf{u}_ u^* \cdot \mathbf{u}_ v^* ) = \frac{1}{2} \cdot \text{SDP最优值}. \] 由于SDP最优值是原整数规划最优值的一个上界（因为SDP是原问题的松弛），因此算法达到了至少0.5的近似比。 6. 举例说明 假设有一个三角形图（三个顶点 \( a, b, c \)，三条边 \( ab, bc, ca \)），权重均为1。整数最优解是选择任意一条边（权重1）。SDP松弛可能给出向量解：例如，取三个互成120°角的单位向量 \( \mathbf{u}_ a, \mathbf{u}_ b, \mathbf{u}_ c \)，则每条边的 \( \frac{1 - \mathbf{u}_ u \cdot \mathbf{u}_ v}{2} = \frac{1 - (-\frac{1}{2})}{2} = \frac{3}{4} \)，SDP目标值为 \( 3 \times \frac{3}{4} = 2.25 \)。随机舍入算法以一定概率输出一条边（期望权重至少为 \( 0.5 \times 2.25 = 1.125 \)），但实际匹配最多一条边，所以期望权重为1，仍然满足近似比0.5。 7. 总结 本示例展示了如何将最大权匹配问题松弛为半定规划，并利用随机舍入得到近似解。该方法的核心在于利用向量几何关系来捕捉匹配的“冲突”约束，并通过随机投影将连续解舍入为整数解。虽然近似比为0.5，不如二分图上的精确算法，但在一般图上这是一种有效的近似方法。