基于线性规划的图最小生成树问题求解示例
题目描述
假设有一个连通无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集合（共 \(n\) 个顶点），\(E\) 是边集合（共 \(m\) 条边）。每条边 \(e \in E\) 有一个权重 \(w_e \geq 0\)。目标是从图中选择一组边，使得所有顶点连通，且总权重最小。要求将该问题建模为线性规划，并解释如何求解。
解题过程
1. 问题建模
最小生成树（MST）问题可以通过整数规划建模，但利用其特殊的组合性质（如基尔霍夫矩阵定理），可以转化为线性规划。以下是基于生成树多面体的线性规划模型：
- 变量：对每条边 \(e \in E\)，定义连续变量 \(x_e \in [0, 1]\)，表示边 \(e\) 是否被选中。
- 目标函数：最小化总权重
\[ \min \sum_{e \in E} w_e x_e. \]
- 约束条件：
- 连通性约束：对任意非空子集 \(S \subset V\)（\(S \neq V\)），至少有一条边连接 \(S\) 和 \(V \setminus S\)：
\[ \sum_{e \in \delta(S)} x_e \geq 1 \quad \forall S \subset V, S \neq \emptyset, \]
其中 $ \delta(S) $ 是 $ S $ 的割边集合（一端在 $ S $、另一端不在 $ S $ 的边）。
- 边数约束：生成树恰好有 \(n-1\) 条边：
\[ \sum_{e \in E} x_e = n-1. \]
- 非负性约束：
\[ x_e \geq 0 \quad \forall e \in E. \]
关键点：该线性规划的最优解中，所有 \(x_e\) 会自动取整数值（0 或 1），无需显式要求整数约束（由生成树多面体的性质保证）。
2. 求解方法：椭球法或内点法
由于约束数量是指数级的（所有子集 \(S\) 的约束），直接使用单纯形法不可行。但可以通过分离 oracle 结合椭球法或内点法求解：
- 分离 oracle：给定一个解 \(x^*\)，检查是否存在 violated constraint（被违反的约束）。
- 对于连通性约束，等价于检查图在边权为 \(x^*_e\) 时的最小割是否小于 1。
- 方法：对每个顶点 \(u\)，计算从 \(u\) 到其他顶点的最大流（最小割）。若某个最小割值 \(<1\)，则返回该约束；否则所有约束满足。
- 算法步骤：
- 初始化一个包含可行解的多面体。
- 调用内点法或椭球法，在每次迭代中通过分离 oracle 检查当前解是否可行。
- 若发现违反约束，将其加入线性规划重新求解；否则当前解即为最优解。
3. 实际应用中的简化
在实践中，MST 问题通常直接使用组合算法（如 Kruskal 或 Prim 算法），但线性规划模型的价值在于：
- 理论上有多项式时间解法（尽管计算复杂）。
- 可扩展至更复杂问题（如带额外约束的生成树）。
- 帮助理解生成树多面体的结构。
4. 示例验证
考虑一个简单图（3 个顶点 \(A, B, C\)，边权：\(AB=2, AC=3, BC=1\)）。
- 线性规划的最优解为 \(x_{BC}=1, x_{AB}=1, x_{AC}=0\)，总权重 3。
- 与 Kruskal 算法结果一致（先选 BC，再选 AB）。
通过此线性规划模型，我们不仅得到了最优解，还验证了生成树问题的凸优化本质。